title: Radiation Hardened Quine

text:
# Question
Title: Radiation Hardened Quine
As you should (hopefully) know, a radiation hardened quine is a quine that you can remove any one character from and still print its original, pre-modified source. The thing is, with most of these you can only remove one character; otherwise everything breaks down. This is where this comes in; your goal is to build a radiation-hardened quine that can take as many character removals as possible. Any language that complies with the rules is fine.

## Rules

* The program must be at least one character long
* The language used must be turing complete (So languages like HQ9+ don't qualify)
* All other rules that apply to normal quines also apply here.
* The solution with the least `program_length^(2/n)` in which *any* set of exactly `n` characters can be removed while still printing the original source code wins.

# Answer
# Perl, ~~1116~~ 1124 bytes, n=3, score=1124^(2/3) or approximately 108.1

**Update**: I've now verified that this works with n=3 via brute force (which took a couple of days); with a program this complex, it's hard to check for radiation-resistance by hand (and I made one mistake in a previous version, which is why the byte count increased). **End update**

I recommend redirecting stderr somewhere that you won't see it; this program produces a ton of warnings about dubious syntax even when you *aren't* deleting characters from it.

It's possible that the program can be shortened. Working on this is fairly painful, making it easy to miss possible micro-optimizations. I was mostly aiming to get the number of deletable characters as high as possible (because that's the really *challenging* part of the program), and treated the tiebreak as something that was nice to aim for but as something I wouldn't put ridiculous effort into optimizing (on the basis that it's very easy to break radiation resistance by accident).

## The program

Note: there's a literal Control-`_` character (ASCII 31) immediately before each of the four occurrences of `-+`. I don't think it copy-and-pasted onto StackOverflow correctly, so you'll have to re-add it before running the program.

```
eval+<eval+<eval+<eval+(q(FoPqOlengthFoBBPP181XXVVVVJJJKKKNdoWchopJFtPDevalMODx4KNFrPIPA-MN-TUV-ZPINFsPIFoPqOI.Fo.IQNevalFoINevalIFsPZyI.Fr.IT-UPINsayDFtJqJFsKPZyPT-UFWrYrKD.DEEEEQDx6NsayDNDforB1..4YforB1..4NexitQNevalFo)=~y=A-Z=-+;-AZz-~=r)####>####>####>####>####>####>
;
;
;
;
eval+<eval+<eval+<eval+(q(FoPqOlengthFoBBPP181XXVVVVJJJKKKNdoWchopJFtPDevalMODx4KNFrPIPA-MN-TUV-ZPINFsPIFoPqOI.Fo.IQNevalFoINevalIFsPZyI.Fr.IT-UPINsayDFtJqJFsKPZyPT-UFWrYrKD.DEEEEQDx6NsayDNDforB1..4YforB1..4NexitQNevalFo)=~y=A-Z=-+;-AZz-~=r)####>####>####>####>####>####>
;
;
;
;
eval+<eval+<eval+<eval+(q(FoPqOlengthFoBBPP181XXVVVVJJJKKKNdoWchopJFtPDevalMODx4KNFrPIPA-MN-TUV-ZPINFsPIFoPqOI.Fo.IQNevalFoINevalIFsPZyI.Fr.IT-UPINsayDFtJqJFsKPZyPT-UFWrYrKD.DEEEEQDx6NsayDNDforB1..4YforB1..4NexitQNevalFo)=~y=A-Z=-+;-AZz-~=r)####>####>####>####>####>####>
;
;
;
;
eval+<eval+<eval+<eval+(q(FoPqOlengthFoBBPP181XXVVVVJJJKKKNdoWchopJFtPDevalMODx4KNFrPIPA-MN-TUV-ZPINFsPIFoPqOI.Fo.IQNevalFoINevalIFsPZyI.Fr.IT-UPINsayDFtJqJFsKPZyPT-UFWrYrKD.DEEEEQDx6NsayDNDforB1..4YforB1..4NexitQNevalFo)=~y=A-Z=-+;-AZz-~=r)####>####>####>####>####>####>
;
;
;
;

```

## The explanation

This program is, quite clearly, made out of four identical smaller programs concatenated together. The basic idea is that each copy of the program will verify whether it's been damaged too badly to run or not; if it has been, it will do nothing (other than possibly spew warnings) and let the next copy run; if it hasn't been (i.e. no deletions, or the character that got deleted was one that makes no difference to the program's operation), it will do its quiny thing (printing out the full program's source code; this is a proper quine, with each part containing an encoding of the entire source code) and then exit (preventing any other undamaged copies from printing the source code out *again* and thus ruining the quine by printing too much text).

Each part is in turn made of two parts which are effectively functionally independent; an outside wrapper and some internal code. As such, we can consider them separately.

### Outside wrapper

The outside wrapper is, basically, `eval<+eval<+eval< ... >####>####...>###` (plus a bunch of semicolons and newlines whose purpose should be pretty obvious; it's to ensure that the parts of the program will remain separated regardless of if some of the semicolons, or the newlines before them, get deleted). This might look fairly simple, but it's subtle in a number of ways, and the reason I picked Perl for this challenge.

First, let's look at how the wrapper functions in an undamaged copy of the program. `eval` parses as a built-in function, which takes one argument. Because an argument is expected, `+` here is a unary `+` (which will be very familiar to Perl golfers by now; they come in useful surprisingly often). We're still expecting an argument (we just saw a unary operator), so the `<` that comes next is interpreted as the start of the `<>` operator (which takes no prefix or postfix arguments, and thus can be used in operand position).

`<>` is a fairly weird operator. Its usual purpose is to read filehandles, and you place the filehandle name *inside* the angle brackets. Alternatively, if the expression isn't valid as a filehandle name, it does globbing (basically, the same process that UNIX shells use to translate text entered by the user to a sequence of command-line arguments; much older versions of Perl actually used the shell for this, but nowadays Perl handles the globbing internally). The intended use, therefore, is along the lines of `<*.c>`, which would typically return a list like `("foo.c", "bar.c")`. In a scalar context (such as the argument to `eval`), it just returns the first entry it finds the first time it's run (the equivalent of the first argument), and would return other entries on hypothetical future runs that never happen.

Now, shells often handle command-line arguments; if you give something like `-r` with no arguments, it'll just be passed to the program verbatim, regardless of whether there's a file with that name or not. Perl acts the same way, so as long as we ensure that there are no characters that are special to the shell or to Perl between the `<` and the matching `>`, we can effectively use this like a really awkward form of string literal. Even better, Perl's parser for quote-like operators has a compulsive tendency to match brackets even in contexts like this one where it makes no sense, so we can nest `<>` safely (which is the discovery needed for this program to be possible). The major downside of all these nested `<>` is that escaping the contents of the `<>` is almost impossible; there seem to be two layers of unescaping with each `<>`, so to escape something on the inside of all three, it needs to be preceded with 63 backslashes. I decided that even though code size is only a secondary consideration in this problem, it almost certainly wasn't worth paying this sort of penalty to my score, so I just decided to write the rest of the program without using the offending characters.

So what happens if parts of the wrapper get deleted?

* Deletions in the word `eval` cause it to turn into a *bareword*, a string with no meaning. Perl doesn't like these, but it treats them as though they were surrounded with quotes; thus `eal<+eval<+...` is interpreted as `"eal" < +eval<+...`. This has no effect on the program's operation, because it's basically just taking the result from the heavily nested evals (which we don't use anyway), casting it to an integer, and doing some pointless comparisons on it. (This sort of thing causes a lot of warning spam as it's clearly not a useful thing to do under normal circumstances; we're just using it to absorb deletions.) This changes the number of closing angle brackets we need (because the opening bracket is now being interpreted as a comparison operator instead), but the chain of comments at the end ensures the string will end safely no matter how many times it's nested. (There are more `#` signs than strictly needed here; I wrote it like I did in order to make the program more compressible, letting me use less data to store the quine.)
* If a `<` gets deleted, the code now parses as `eval(eval<...>)`. The secondary, outside `eval` has no effect, because the programs we're evaluating don't return anything that has any real effects as a program (if they return normally at all, it's normally a null string or a bareword; more commonly they return via exception, which causes `eval` to return a null string, or use `exit` to avoid returning at all).
* If a `+` gets deleted, this has no immediate effect if the adjacent code is intact; unary `+` has no effect on the program. (The reason the original `+`s are there is to help repair damage; they increase the number of situations in which `<` is interpreted as a unary `<>` rather than as a relational operator, meaning you need more deletions to produce an invalid program.)

The wrapper *can* be damaged with enough deletions, but you need to do a series of deletions in order to produce something that doesn't parse. With four deletions, you can do this:

```
eal<evl<eval+<...

```

and in Perl, the relational operator `<` is nonassociative, and thus you get a syntax error (the same one you'd get with `1<2<3`). As such, the cap for the program as written is n=3. Adding more unary `+`s seems like a promising way to increase it, but as that'd make it increasingly likely that the inside of the wrapper could break too, verifying that the new version of the program works could be very difficult.

The reason the wrapper is so valuable is that `eval` in Perl catches exceptions, such as (for example) the exception that you get when you try to compile a syntax error. Because this `eval` is of a string literal, the compile of the string happens at runtime, and if the literal fails to compile, the resulting exception gets caught. This causes `eval` to return a null string and set the error indicator `$@`, but we never check either (except by occasionally executing the returned null string in a few mutated versions of the program). Crucially, this means that if something should happen to the code *inside* the wrapper, causing a syntax error, then the wrapper will just cause the code to do nothing instead (and the program will keep executing in an attempt to find an undamaged copy of itself). Therefore, the inside code doesn't have to be nearly as radiation-proof as the wrapper; all that we care about is that if damaged, it'll either act identically to the nondamaged version of the program, or else it'll crash (allowing `eval` to catch the exception and continue) or exit normally without printing anything.

### Inside the wrapper

The code inside the wrapper, fundamentally, looks like this (again, there's a Control-`_` that Stack Exchange won't show immediately before the `-+`):

```
eval+(q(...)=~y=A-Z=-+;-AZz-~=r)

```

This code is written entirely with glob-safe characters, and its purpose is to add a new alphabet of punctuation marks that make it possible to write a real program, via transliterating and evaluating a string literal (we can't use `'` or `"` as our quote marks, but `q(``)` is also a valid way to form a string in Perl). (The reason for the unprintable character is that we need to transliterate something into the space character without a literal space character in the program; thus we form a range starting at ASCII 31, and catch the space as the second element of the range.) Obviously, if we're producing some characters via transliteration, we have to sacrifice characters to transliterate them *from*, but uppercase letters aren't very useful and it's much easier to write without access to those than without access to punctuation marks.

Here's the alphabet of punctuation marks that become available as a result of the glob (the upper line shows the encoding, the lower line the character it encodes):

```
BCDEFGHIJKLMNOPQRSTUVWXYZ
 !"#$%&'()*+;<=>?@AZz{|}~

```

Most notably, we have a bunch of punctuation marks that aren't glob-safe but are useful in writing Perl programs, together with the space character. I also saved two uppercase letters, the literal `A` and `Z` (which encode not to themselves, but to `T` and `U`, because `A` was needed as an upper as well as a lower range endpoint); this allows us to write the transliteration instruction itself using the new encoded character set (although uppercase letters aren't that useful, they're useful in specifying changes to the uppercase letters). The most notable characters that we don't have available are `[`, `\`, and `]`, but none are needed (when I needed a newline in the output, I produced it using the implicit newline from `say` rather than needing to write `\n`; `chr 10` would also have worked but is more verbose).

As usual, we need to worry about what happens if the inside of the wrapper gets damaged outside the string literal. A corrupted `eval` will prevent anything running; we're fine with that. If the quote marks get damaged, the inside of the string isn't valid Perl, and thus the wrapper will catch it (and the numerous subtractions on strings mean that even if you could make it valid Perl, it'd do nothing, which is an acceptable outcome). Damage to the transliteration, if it isn't a syntax error, will mangle the string being evaluated, typically causing *it* to become a syntax error; I'm not 100% sure there are no cases in which this breaks, but I'm brute-forcing it at the moment to make sure, and it should be easy enough to fix if there are.

### The encoded program

Looking inside the string literal, reversing the encoding I used, and adding whitespace to make it more readable, we get this (again, imagine a control-underscore before the `-+`, which is encoded as `A`):

```
$o=q<
  length$o  ==181 || zzzz((()));
  do {
    chop ($t = "eval+<"x4);
    $r = '=-+;-AZz-~=';
    $s = '$o=q<' . $o . '>;eval$o';
    eval '$s=~y' . $r . 'A-Z=';
    say "$t(q($s)=~y=A-Z${r}r)" . "####>"x6;
    say ";" for 1..4
  } for 1..4;
  exit>;
eval $o

```

People who are used to quines will recognise this general structure. The most crucial part is at the start, where we verify that $o is undamaged; if characters have been deleted, its length won't match `181`, so we run `zzzz((()))` which, if it isn't a syntax error due to unmatched brackets, will be a runtime error even if you delete any three characters, because none of `zzzz`, `zzz`, `zz`, and `z` is a function, and there's no way to prevent it parsing as a function other than deleting `(((` and causing an obvous syntax error. The check itself is also immune to damage; the `||` can be damaged to `|` but that will cause the `zzzz((()))` call to run unconditionally; damaging variables or constants will cause a mismatch because you're comparing one of `0`, `180`, `179`, `178` for equality to some subset of the digits of `181`; and removing one `=` will cause a parse failure, and two `=` to inevitably cause the LHS to evaluate to either integer 0 or a null string, both of which are falsey.

**Update**: This check was slightly wrong in a preceding version of the program, so I had to edit it to fix the issue. The previous version looked like this after the decode:

```
length$o==179||zzzz((()))

```

and it was possible to delete the first three punctuation marks to get this:

```
lengtho179||zzz((()))

```

`lengtho179`, being a bareword, is truthy and thus breaks the check. I fixed this by adding an extra two `B` characters (which encode space characters), meaning the latest version of the quine does this:

```
length$o  ==181||zzzz((()))

```

Now it's impossible to hide both the `=` signs and the `$` sign without producing a syntax error. (I had to add two spaces rather than one because a length of `180` would put a literal `0` character into the source, which could be abused in this context to integer-compare zero with a bareword, which succeeds.) **End update**

Once the length check passes, we know the copy is undamaged, at least in terms of character deletions from it, so it's all just straightforward quining from there (substitutions of punctuation marks due to a corrupted decoding table wouldn't be caught with this check, but I've already verified via brute-forcing that no three deletions from *only* the decoding table break the quine; presumably most of them cause syntax errors). We have `$o` in a variable already, so all we need to do is hardcode the outside wrappers (with some small degree of compression; I didn't skip out the part of the question *entirely*). One trick is that we store the bulk of the encoding table in `$r`; we can either print it literally in order to generate the encoding table section of the inside wrapper, or concatenate some code around it and `eval` it in order to run the decoding process in reverse (allowing us to figure out what the *encoded* version of $o is, having only the *decoded* version available at this point).

Finally, if we were an intact copy and thus could output the entire original program, we call `exit` in order to prevent the other copies also trying to print the program out.

## Verification script

Not very pretty, but posting it because someone asked. I ran this several times with a variety of settings (typically changing `$min` and `$max` to check for various areas of interest); it wasn't a fully automated process. It has a tendency to stop running due to heavy CPU load elsewhere; when this happened, I just changed `$min` to the first value of `$x` that wasn't fully checked and continued running the script (thus ensuring that all the programs in the range got checked eventually). I only checked deletions from the first copy of the program, because it's fairly obvious that deletions from the other copies can't do more.

```
use 5.010;
use IPC::Run qw/run/;
undef $/;
my $program = <>;
my $min = 1;
my $max = (length $program) / 4 - 3;
for my $x ($min .. $max) {
    for my $y ($x .. $max) {
        for my $z ($y .. $max) {
            print "$x, $y, $z\n";
            my $p = $program;
            substr $p, $x, 1, "";
            substr $p, $y, 1, "";
            substr $p, $z, 1, "";
            alarm 4;
            run [$^X, '-M5.010'], '<', \$p, '>', \my $out, '2>', \my $err;
            if ($out ne $program) {
                print "Failed deleting at $x, $y, $z\n";
                print "Output: {{{\n$out}}}\n";
                exit;
            }
        }
    }
}

say "All OK!";

```
> 64 votes

# Answer
## Befunge-98, 884, n = 14, score ≈ 2.636

```
f00f00f00f00f00f00f00f00f00f00f00f00f00f00f0xxxxxxxxxxxxxxx"""""""""""""""fffffffffffffff'''''''''''''''000000000000000\\\\\\\\\\\\\\\'''''''''''''''000000000000000\\\\\\\\\\\\\\\'''''''''''''''fffffffffffffff\\\\\\\\\\\\\\\111111111111111---------------:::::::::::::::!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!000000000000000aaaaaaaaaaaaaaa---------------bbbbbbbbbbbbbbb---------------***************jjjjjjjjjjjjjjj$$$$$$$$$$$$$$$'''''''''''''''+++++++++++++++kkkkkkkkkkkkkkk,,,,,,,,,,,,,,,333333333333333kkkkkkkkkkkkkkk$$$$$$$$$$$$$$$000000000000000{{{{{{{{{{{{{{{'''''''''''''''888888888888888uuuuuuuuuuuuuuu'''''''''''''''!!!!!!!!!!!!!!!111111111111111+++++++++++++++'''''''''''''''xxxxxxxxxxxxxxx###############;;;;;;;;;;;;;;;:::::::::::::::!!!!!!!!!!!!!!!kkkkkkkkkkkkkkk@@@@@@@@@@@@@@@dddddddddddddddkkkkkkkkkkkkkkk:::::::::::::::eeeeeeeeeeeeeeekkkkkkkkkkkkkkk,,,,,,,,,,,,,,,;;;;;;;;;;;;;;;

```

Try it online!

This doesn't just work when you remove exactly 14 characters, but even when you remove any amount *up to* 14 characters.

`n = 14` may seem like a very arbitrary choice, but the technique I used can in fact only be used for radiation-hardening orders from 1 to 14, but not easily beyond that (it might be possible but I have no clue how). The order-1 quine is merely 73 bytes (although it employs some golfing tricks that don't apply to larger `n`):

```
200 20 xx""''ÈÈ..aa22**..33kk$$00{{''!!uu''!!11++''xx##;;::!!kk@@::,,,,;;

```

### Explanation

When I was working on this answer I found that it's possible to set the instruction pointer's delta to `(2,0)` under radiation-hardened conditions with the following snippet:

```
20020xx

```

See that answer for why this works. I found this just with a bit of fiddling by hand, but this raised the question whether there are similar patterns which are robust under removal of multiple characters. So I wrote a short Mathematica script to search for these by brute force:

```
n = 14;
m = 4;
Print @ FromDigits @ {
      m + 1, 0,
      ## & @@ ((m + 1) IntegerDigits[#, 2, n - 4]),
      m + 1, 0
} & /@ Select[
   Range[0, 2^(n - 4) - 1],
   AllTrue[
     Subsets[{
         m + 1, 0,
         ## & @@ ((m + 1) IntegerDigits[#, 2, n - 4]),
         m + 1, 0
       },
       {n - m, n - 1}
     ] //. {a___, _, m + 1} | {a___, 0, _} :> {a},
     MatchQ@{___, m + 1, 0}
  ] &
];

```

This very quickly revealed a pattern. To get a corresponding snippet which works for removal of up to `n` characters, you can use `(m0x){n}m0` where `m` is `n+1` and `x` is either `m` or `0`. So all of the following would work for removal of up to two characters:

```
30030030
30030330
30330030
30330330

```

I'm sure it's possible to prove this, but I've simply verified for `n` up to `7`. Of course, this only works as long as we can represent `n+1` as a single digit, and the largest such digit in Befunge 98 is `f` which represents 15. That's why my approach is limited to `n = 14`. If someone finds a way to reliably set the delta to larger `n+1`, it would likely be possible to increase the order of this radiation-hardened quine indefinitely.

Let's look at the actual code. There are basically two parts to it. First we set the delta to `(15,0)` as I just mentioned:

```
f00f00f00f00f00f00f00f00f00f00f00f00f00f00f0xxxxxxxxxxxxxxx

```

And the remainder of the code has each command repeated 15 times and prints the source. If we remove the repetition, it looks like this:

```
"f'0\'0\'f\1-:!!0a-b-*j$'+k,3k$0{'8u'!1+'x#;:!k@dk:ek,;

```

The `"` is a standard 2D quining technique: it starts string mode, pushes all the characters (except itself) onto the stack and ends string mode again after wrapping around. This helps us get all the code points of the second half, but it will fail to get us anything useful from the first half, because throughout the `f00f00...f0` bit, it will only record two characters (which may be either `f` or `0` depending on which characters are deleted). But since that part isn't made up of characters being repeated 15 times, we'll need to print it separately anyway.

More conveniently, in the unmodified quine, the length of the string before the `"` is `-1 (mod 15)`. This guarantees that no matter how many characters (up to 14) we remove, that the *number* of characters recorded there is always 3 (one `x` and two of `f` and `0`). This is actually true for any radiation order up to 14.

We now start by printing the `f00f00...f0` part:

```
f'0\'0\'f\1-:!!0a-b-*j$'+k,

f          Push 15, a loop counter.
'0\'0\'f\  Put "00f" underneath the loop counter.
1-         Decrement the loop counter.
:!!        Copy it, and turn it into a 1 if it's positive.
0a-b-      Push -21.
*          Multiply by 0 if the loop counter is zero, or by 1 otherwise.
j          Jump that many steps. If the value was 0, this is a no-op and
           the loop ends. Otherwise, this brings us back after the f.
$          Pop the loop counter (which is now 0).
'+k,       Print the top of the stack 43 times, which gives us all of
           the "f00f00...f0" and leaves one "0" on top of the stack.

```

The next `3k$` simply discards that `0` as well as the three characters that were pushed by `"` from the beginning of the program. The stack now contains only the characters after the `"` as well as some junk underneath from the original `f00f00...f0` depending on which characters were deleted.

Now we just need to reverse the top of the stack (containing the remaining characters) and print each one of them 15 times.

```
0{     Start a new, empty stack. This pushes two zeros onto the original stack.
'8u    Move the top 56 values from the original stack to the new one, which
       is the 54 characters after the " as well as those two zeros. This is
       implemented as pop-push loop, so it reverses the order of those elements.
'!1+   Push a " by incrementing a !.
'x     Push an x. Now we've got all the characters that are repeated 15 times.
#;     Enter a loop. This is a standard technique for Befunge-98: the ; is
       a bit like a comment character, that ignores everything until the next
       ;, but we jump over the first one with #, so that from now on only
       the code inside will be executed (over and over).
  :!     Copy the top of the stack, and compute logical NOT (1 if 0, 0 otherwise).
  k@     Terminate the program that many times (i.e. when the top of the
         stack is zero).
  dk:    Make 14 copies of the top of the stack.
  ek,    Print 15 characters from the top of the stack.
;

```

And that's it. :)
> 43 votes

# Answer
# JavaScript (ES6), 927 bytes, n=1, score=859329

*note: don't use a REPL (like a browser console) to run this.*

This was written before code length was a factor, so it isn't golfed yet.

This was *very* difficult, and deserves a thorough explanation. Which I will write later, after I explore this challenge a little more!

```
etTimeout=stTimeout=seTimeout=setimeout=setTmeout=setTieout=setTimout=setTimeut=setTimeot=setTimeou=unescape=>42;
setTimeout
`c="function f(){x=String.fromCharCode(96);n=String.fromCharCode(10);q=String.fromCharCode(34);y='etTimeout=stTimeout=seTimeout=setimeout=setTmeout=setTieout=setTimout=setTimeut=setTimeot=setTimeou=unescape=>42;'+n;z='setTimeout'+n+x+'c='+q+f+';f();_=1'+q+';if(window._);else if(c.length>339)eval(c)//'+x+'///'+x+n+n;console.log(y+z+z)};f();_=1";if(window._);else if(c.length>339)eval(c)//`///`

setTimeout
`c="function f(){x=String.fromCharCode(96);n=String.fromCharCode(10);q=String.fromCharCode(34);y='etTimeout=stTimeout=seTimeout=setimeout=setTmeout=setTieout=setTimout=setTimeut=setTimeot=setTimeou=unescape=>42;'+n;z='setTimeout'+n+x+'c='+q+f+';f();_=1'+q+';if(window._);else if(c.length>339)eval(c)//'+x+'///'+x+n+n;console.log(y+z+z)};f();_=1";if(window._);else if(c.length>339)eval(c)//`///`

```

*note: there is a trailing newline*

Basically, the first line is carefully constructed to rename all 'mispellings' of `setTimeout` to valid functions, so that if a character is removed from one of the `setTimeout`s the code will not error out and the unscathed version can run. It is also written so that if any one character is removed from the first line, there will be no error and the rest of the code can run unaffected.

The second and third blocks are exactly equivalent. If one runs to completion, it sets the `_` variable so that the other knows not to duplicate the quine. If one of these blocks errors out, it does not affect the other block because it was called asynchronously using `setTimeout`. The error will cause `_` not to be set, so the other block will quine successfully. The main code is in a string, which is checked for length in each block to make sure that there were no removals.

Template strings on the next line with some comments at the end of the template strings protects the code from erroring out if one of the backticks forming the template string is removed. If the ending backtick is removed, the template string is ended by the backtick in the comment. If the starting backtick is removed, setTimeout is evaluated as an unassigned function (a no-op) and the code runs as normal, without a setTimeout. The ending backtick is nullified by another comment.

**What's that you say? You want to try it out? Say no more!**

Full page mode recommended.

Ignore the input box, this snippet takes no input.

Try removing any one character from the code!

Don't believe it? Normal code will still work (but it won't quine...) Try something like `console.log(5)`!

*note: the snippet had to be modified slightly to disable the REPL feature, so I removed multiple output capabilities for this answer only.*

```
etTimeout=stTimeout=seTimeout=setimeout=setTmeout=setTieout=setTimout=setTimeut=setTimeot=setTimeou=unescape=>42;
setTimeout
`c="function f(){x=String.fromCharCode(96);n=String.fromCharCode(10);q=String.fromCharCode(34);y='etTimeout=stTimeout=seTimeout=setimeout=setTmeout=setTieout=setTimout=setTimeut=setTimeot=setTimeou=unescape=>42;'+n;z='setTimeout'+n+x+'c='+q+f+';f();_=1'+q+';if(window._);else if(c.length>339)eval(c)//'+x+'///'+x+n+n;console.log(y+z+z)};f();_=1";if(window._);else if(c.length>339)eval(c)//`///`

setTimeout
`c="function f(){x=String.fromCharCode(96);n=String.fromCharCode(10);q=String.fromCharCode(34);y='etTimeout=stTimeout=seTimeout=setimeout=setTmeout=setTieout=setTimout=setTimeut=setTimeot=setTimeou=unescape=>42;'+n;z='setTimeout'+n+x+'c='+q+f+';f();_=1'+q+';if(window._);else if(c.length>339)eval(c)//'+x+'///'+x+n+n;console.log(y+z+z)};f();_=1";if(window._);else if(c.length>339)eval(c)//`///`
```

```
<!--                               Try the test suite below!                              --><strong id="bytecount" style="display:inline; font-size:32px; font-family:Helvetica"></strong><strong id="bytediff" style="display:inline; margin-left:10px; font-size:32px; font-family:Helvetica; color:lightgray"></strong><br><br><pre style="margin:0">Code:</pre><textarea id="textbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><pre style="margin:0">Input:</pre><textarea id="inputbox" style="margin-top:5px; margin-bottom:5px"></textarea><br><button id="testbtn">Test!</button><button id="resetbtn">Reset</button><br><p><strong id="origheader" style="font-family:Helvetica; display:none">Original Code Output:</strong><p><div id="origoutput" style="margin-left:15px"></div><p><strong id="newheader" style="font-family:Helvetica; display:none">New Code Output:</strong><p><div id="newoutput" style="margin-left:15px"></div><script type="text/javascript" id="golfsnippet">var bytecount=document.getElementById("bytecount");var bytediff=document.getElementById("bytediff");var textbox=document.getElementById("textbox");var inputbox=document.getElementById("inputbox");var testbtn=document.getElementById("testbtn");var resetbtn=document.getElementById("resetbtn");var origheader=document.getElementById("origheader");var newheader=document.getElementById("newheader");var origoutput=document.getElementById("origoutput");var newoutput=document.getElementById("newoutput");textbox.style.width=inputbox.style.width=window.innerWidth-50+"px";var _originalCode=null;function getOriginalCode(){if(_originalCode!=null)return _originalCode;var allScripts=document.getElementsByTagName("script");for(var i=0;i<allScripts.length;i++){var script=allScripts[i];if(script.id!="golfsnippet"){originalCode=script.textContent.trim();return originalCode}}}function getNewCode(){return textbox.value.trim()}function getInput(){try{var inputText=inputbox.value.trim();var input=eval("["+inputText+"]");return input}catch(e){return null}}function setTextbox(s){textbox.value=s;onTextboxChange()}function setOutput(output,s){output.innerHTML=s}function addOutput(output,data){output.innerHTML='<pre style="background-color:'+(data.type=="err"?"lightcoral":"lightgray")+'">'+escape(data.content)+"</pre>"}function getByteCount(s){return(new Blob([s],{encoding:"UTF-8",type:"text/plain;charset=UTF-8"})).size}function onTextboxChange(){var newLength=getByteCount(getNewCode());var oldLength=getByteCount(getOriginalCode());bytecount.innerHTML=newLength+" bytes";var diff=newLength-oldLength;if(diff>0){bytediff.innerHTML="(+"+diff+")";bytediff.style.color="lightcoral"}else if(diff<0){bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgreen"}else{bytediff.innerHTML="("+diff+")";bytediff.style.color="lightgray"}}function onTestBtn(evt){origheader.style.display="inline";newheader.style.display="inline";setOutput(newoutput,"");setOutput(origoutput,"");var input=getInput();if(input===null){addOutput(origoutput,{type:"err",content:"Input is malformed. Using no input."});addOutput(newoutput,{type:"err",content:"Input is malformed. Using no input."});input=[]}doInterpret(getNewCode(),input,function(data){addOutput(newoutput,data)});doInterpret(getOriginalCode(),input,function(data){addOutput(origoutput,data)});evt.stopPropagation();return false}function onResetBtn(evt){setTextbox(getOriginalCode());origheader.style.display="none";newheader.style.display="none";setOutput(origoutput,"");setOutput(newoutput,"")}function escape(s){return s.toString().replace(/&/g,"&").replace(/</g,"<").replace(/>/g,">")}window.alert=function(){};window.prompt=function(){};function doInterpret(code,input,cb){var workerCode=interpret.toString()+";function stdout(s){ self.postMessage( {'type': 'out', 'content': s} ); }"+" function stderr(s){ self.postMessage( {'type': 'err', 'content': s} ); }"+" function kill(){ self.close(); }"+" self.addEventListener('message', function(msg){ interpret(msg.data.code, msg.data.input); });";var interpreter=new Worker(URL.createObjectURL(new Blob([workerCode])));interpreter.addEventListener("message",function(msg){cb(msg.data)});interpreter.postMessage({"code":code,"input":input});setTimeout(function(){interpreter.terminate()},1E4)}setTimeout(function(){getOriginalCode();textbox.addEventListener("input",onTextboxChange);testbtn.addEventListener("click",onTestBtn);resetbtn.addEventListener("click",onResetBtn);setTextbox(getOriginalCode())},100);function interpret(code,input){_=undefined;window={};alert=function(s){stdout(s)};window.alert=alert;console.log=alert;prompt=function(s){if(input.length<1)stderr("not enough input");else{var nextInput=input[0];input=input.slice(1);return nextInput.toString()}};window.prompt=prompt;(function(){try{_=undefined;eval(code);if(typeof evalResult=="disabled_function_evaluation"){var callResult=evalResult.apply(this,input);if(typeof callResult!="undefined")stdout(callResult)}}catch(e){stderr(e.message)}})()};</script>
```

A better explanation is forthcoming. In the meantime feel free to ping me in chat @jrich with any comments/questions/criticisms!
> 18 votes

---
Tags: code-challenge, quine, radiation-hardening
---


# Question
Title: Output subdivisions of international standard paper sizes
**ISO Paper Sizes Defined:**

The A series paper sizes are defined by the following requirements:

```
The length divided by the width is the square root of 2.
The A0 size has an area of 1 unit.
Each subsequent size A(n) is defined as A(n-1) cut in half parallel to its shorter sides.

```

**Task:**

given an input `f[n]` output A0 divided into `n` subdivisions.

**Test cases:**

`f[1]` to `f[12]`:

*Here, A0 is given by* `f[1]`*, but this indexing isn't essential.*

**Winning criteria:**

The shortest code in bytes wins.

# Answer
# BBC BASIC 49 ASCII characters

**Tokenised filesize 44 bytes**

```
I.n:F.i=0TOn:RECTANGLE0,0,1189>>i/2+.5,841>>i/2N.

```

Much shorter than before! I always forget about the bitshift operators in BBC BASIC for windows as they weren't available on my old computer back in the day.

# BBC BASIC 63 ASCII characters

**Tokenised filesize 58 bytes**

Dowload interpreter at http://www.bbcbasic.co.uk/bbcwin/download.html

```
A%=841C%=1189d=4I.n:F.i=0TOn:RECTANGLE0,0,C%,A%:d!^B%/=2d=-d:N.

```

Uses zero indexing, which I prefer. Thus 0 outputs the paper for A0, 1 outputs A0 divided into a pair of A1s, etc.

It is necessary to alternate between halving the X and Y coordinates, but doing that in an array would have cost too many bytes. Instead I use the fact that BBC basic has a block of static integer variables `A%..Z%` of 4 bytes each stored in contiguous memory. I store the X and Y values in `A%` and `C%` and access using the pointer to `%B` modified by the value of d, which alternates between `4` and `-4`.

**Ungolfed**

```
  A%=841
  C%=1189
  d=4
  INPUTn
  FORi=0TOn
    RECTANGLE0,0,C%,A%
    d!^B%/=2
    d=-d
  NEXT

```

**Output**
> 2 votes

# Answer
## JavaScript (ES6) + HTML, ~~96~~ 94 + 34 = ~~130~~ 128 bytes

```
f=(n,w=297,h=210)=>n--&&f(n,h<w?w/2:w,h<w?h:h/2,(C=c.getContext`2d`).rect(0,0,w,h),C.stroke())

f(8)
```

```
<canvas id=c width=300 height=300>
```
> 4 votes

# Answer
# Mathematica, ~~87~~ 85 bytes

Thanks @martin for 1 byte.

```
Graphics@{EdgeForm@Thin,White,Rectangle[#,0{,}]&/@NestList[Sort[#/a]&,{1,a=√2},#]}&

```
> 2 votes

# Answer
## JavaScript (ES6)/SVG (HTML5), 170 bytes

```
a=prompt();document.write('<svg width=297 height=210>');for(w=297,h=210;a--;h>w?h/=2:w/=2)document.write(`<rect fill=none stroke=#000 x=0 y=0 width=${w} height=${h} />`);
```

Uses 1-based indexing.
> 2 votes

---
Tags: code-golf, graphical-output, recursion
---


title: Binary to trinary

text:
# Question
Title: Binary to trinary
# The problem

Given a binary number from 0 to 111111 convert it to trinary. (Base 3). Then print the result.

## Rules

No using a list of conversions.

Don't cheat

You must use a string as the number

No compressing the input string As I will be testing the code with several different numbers I can't use compressed strings

## Notes

By trinary I mean counting in base 3. So 0,1,2,10,11,12,20... ect

Leading zeros will be present 001101

Most important number is on the left.

## Example

```
String input = "110111"
String a = code(input);
print(a);

```

# To win

This is code golf!

Do it correctly and in the smallest size.

# Answer
> 1 votes
# Bash 25 bytes

**Golfed**

```
bc<<<"ibase=2;obase=3;$1"

```

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

```
s=>(+`0b${s}`).toString(3)

```

# Answer
> 1 votes
# Ruby, ~~97~~ 87 bytes

```
f=->a{x=0
a.chars.map{|i|x+=x+i.ord%2}
o=x>0?"":?0
(o=(48+x%3).chr+o
x/=3)while x>0
o}

```

Old version:

```
def f a
x=0
a.chars.map{|i|x=x+x+i.ord%2}
o=x>0?"":"0"
while x>0
o=(48+x%3).chr+o
x/=3
end
o
end

```

---
Tags: code-golf, parsing
---


title: Read a crossword with a twist!

text:
# Question
Title: Read a crossword with a twist!
Similar to this question, but this is a crossword variation!

Instead of only one letter per grid square, you can have *one **or** two*.

# Input:

* A 2d array, or whatever works in your language.
* You can assume valid inputs
* Any array size must work

# Output:

* An array of all the words
    + Across and down
    + All words must be joined together, i.e. linked in an unbroken chain of words (if not return false)
    + Words must be at least two *grid squares*, not letters

### Example:

```
[["",  "wo", "r",  "k"],
[ "",   "r",  "",   ""],
[ "he", "l",  "lo", ""],
[ "",   "d",  "ad", ""]]

```

### Returns:

```
["work", "world", "hello", "load", "dad"]

```

### Example:

```
[["he", "ll", "o"],
[ "",   "",   ""],
[ "wo", "r",  "ld"]]

```

### Returns:

```
false

```

This is , so I'll be running this on windows 7 with 2.5ghz and 16gb of ram. If your code is really esoteric, provide a link to the compiler so I can actually run it.

# Answer
> 1 votes
# Python 3

```
import numpy
from scipy.ndimage import measurements

def crosswords(arr):
    M=numpy.asarray(arr)
    # check connectivity
    if measurements.label(numpy.where(M!='',1,0))[-1] != 1:
        return 'false'

    words = []
    def get_words(mat):
        for r in mat:
            word,counter='',0
            for c in r:
                if c=='':
                    if counter>1:
                        words.append(word)
                    word, counter = '', 0
                else:
                    word, counter = word+c, counter+1
            if counter > 1:
                words.append(word)
    get_words(M)
    # transpose M
    get_words(M.T)
    return words

```

# Usage:

Function takes an array of array of strings as input:

`crosswords(
[["", "wo", "r", "k"],
[ "", "r", "", ""],
[ "he", "l", "lo", ""],
[ "", "d", "ad", ""]])`

Returns the string `false` when connectivity returns multiple labels. Returns array of valid words otherwise.

I timed it with `timeit`, `time.time()` and using the console command `time` and but I don't know which one to use or which one to post here.

---
Tags: string, fastest-code, crossword
---


title: Busy Brain Beaver reboot

text:
# Question
Title: Busy Brain Beaver reboot
## Introduction

I found a really interesting puzzle it was called Busy Brain Beaver. But it has been 3 years since the latest activity and there are some things I didn't like about it. So I decided to make a new one.

## The Rules

I want this one to be more brainfuck focused:

* Your goal is to make a brainfuck program that outputs the biggest number.
* It has to output that number in finite time so you can't say `+[+].` outputs infinity (it doesn't have to terminate ex: `+.[+]` is OK)
* Your program can only be 500 useful characters(non-brainfuck characters don't count)
* You can assume `.` outputs your number (in decimal notation).
* Only the first output counts (so you can't say `+[+.]` outputs infinity)
* You can't ask for input so `,` is ignored
* This takes place in a special brainfuck environment:
    + There are an infinite amount of cell to the left and to the right.
    + All cells start at 0
    + All cells can hold **any** integer (so `-` at 0 becomes -1)
* Give an approximation (lower bound) for which number your program would output (given an arbitrarily finite time) (if you are using a special notation please say which one or provide a link)
* An explanation of your algorithm would be appreciated. (posting the formatted and commented version will be appreciated too)

### Not a duplicate

It was marked as a possible duplicate of Largest Number Printable I think this is different because:

* This question is brainfuck focused. And in largest number printable brainfuck isn't even allowed. Yes they are both a busy beaver. But if you think these two are duplicates then any two busy beavers are duplicates. The difference between a brainfuck contest and a non-brainfuck contest is really big. And before it got closed people seemed to have a lot of interest in this one.
* The goal here is to output a long number not a lot of bytes

## Leader Board (top 10)

1. Gabriel Benamy 2↑↑↑411
2. Mike Bufardeci 4277772 = 163\*(162\*162)
3. fejfo 60762 = 246\*247

# Answer
> 9 votes
# 22222222... (65536 twos) = 2↑↑↑4

Before I begin, this is not the largest number expressible using 500 bytes of New Brainfuck. It's simply where I gave up trying to wrap my head around how big the numbers were getting. **This answer only uses 93 bytes** and is therefore not the largest number, but it's proof of concept that mind-bogglingly large numbers are possible.

```
+++[->++[->+>+<<]>>[-<<+>>]+<[->[-<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<]>[-<+>]<<]>[-<+>]<<<]>>.

```

This is a modification of the exponentiation algorithm in Brainfuck.

This number is so large, it's almost impossible to describe in human terms. It isn't sufficient to say "the number has this many digits" because it has more digits than particles in the universe. In fact, the number of digits this number contains has more digits than the number of particles in the universe.

Let this number be x, and let `f(0) = x`. Recursively define `f(n) = floor[log10[f(n-1)]]`. The first *n* which is smaller than 1 googol is over 10,000.

This answer is 93 bytes.

If we removed removed a single leading `+`, the result would be `65536` = 2222. Removing another `+` gives us 4. This means that if we add another +, we would get a number tower with 2↑↑↑4 twos, which would be 2↑↑↑5. That answer would be 94 bytes. If I were to add another 406 plus signs to this, we would get 2↑↑↑411, which is mind-bogglingly big. Instead, if I were to add yet another outer loop, I could probably get something close to 2↑↑↑↑380. For the record, 2↑↑↑↑3 = 2↑↑↑4, and 2↑↑↑↑4 dwarfs 2↑↑↑4 much the same way that 2↑↑↑4 dwarfs 65536. In fact, it may just be possible to actually get close to Graham's Number using 500 bytes of brainfuck.

# Answer
> 1 votes
# 4277772 = 163\*(162\*162)

```
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-]<-]>>.

```

As a reaction to the 60762 solution this is another simple solution. Here we multiply just like that answer but inside of another loop. I am somewhat concerned that I am interpreting this nested loop incorrectly but I think that this is correct and the output would be 4,277,772.

The loop looks like the code below except the first `+` is replaced with 163 `+`s and the other two `+`s are replaced with 162 `+`s:

```
+[>+[>+<-]<-]>>.

```

# Answer
> 0 votes
# 499

```
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

```

The naive approach, increments the starting cell 499 times before outputting that cell and terminating. I would submit a more complex answer, but there are no online testbeds for this variant of brainfuck and I do not want to post an answer that doesn't work.

# Answer
> 0 votes
# 60762 = 246\*247

As a reaction on the 499 solution I will do an other very simple solution it just multiplies 2 numbers

```
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<-]>.

```

how it works is pretty self explanatory it uses the standard multiplication loop ++\[\>+++\<-\]\>. would be 2\*3 = 6

---
Tags: code-challenge, number, brainfuck, busy-beaver
---


title: Array unification

text:
# Question
Title: Array unification
## Introduction

Consider two arrays of the same length, say `A = [0,1,0,2]` and `B = [-1,1,2,2]`. Suppose we know that their contents are equivalent in some sense, item by item:

* `0` is equivalent to `-1`,
* `1` is equivalent to `1`,
* `0` is equivalent to `2`, and
* `2` is equivalent to `2`.

Equivalence is transitive: `-1` and `0` are equivalent, and `0` and `2` are equivalent, so `-1` and `2` are also equivalent. The *unification* of `A` and `B` is the array where each item of `A` (or `B`) has been replaced by the largest number that's equivalent to it. In this case, the unification would be `[2,1,2,2]`.

## The task

Write a program or function that takes two non-empty integer arrays of equal length, and outputs their unification. You can also modify one of the inputs in place instead of returning. The lowest byte count wins.

## Test cases

```
[0] [0] -> [0]
[1] [2] -> [2]
[0,-1] [-1,-1] -> [0,0]
[0,1,0] [2,1,0] -> [2,1,2]
[1,2,3] [0,0,1] -> [3,3,3]
[0,1,0,2] [-1,1,2,2] -> [2,1,2,2]
[1,0,1,-4] [-3,-1,-2,2] -> [1,0,1,2]
[1,2,3,-2] [1,0,-3,-2] -> [1,2,3,-2]
[-3,-2,-1,0,1] [-1,-1,-1,-1,-1] -> [1,1,1,1,1]
[-3,-2,-1,0,1] [2,-1,0,1,-3] -> [2,2,2,2,2]
[-3,5,5,3,1] [4,2,3,1,2] -> [4,5,5,5,5]
[4,0,2,-5,0] [0,4,-5,3,5] -> [5,5,3,3,5]
[-2,4,-2,3,2,4,1,1] [-2,4,1,2,2,3,1,-2] -> [1,4,1,4,4,4,1,1]
[-10,-20,-11,12,-18,14,-8,-1,-14,15,-17,18,18,-6,3,1,15,-15,-19,-19] [-13,6,-4,3,19,1,-10,-15,-15,11,6,9,-11,18,6,6,-5,-15,7,-11] -> [-8,14,18,14,19,14,-8,-1,-1,15,14,18,18,18,14,14,15,-1,18,18]
[20,15,2,4,-10,-4,-19,15,-5,2,13,-3,-18,-5,-6,0,3,-6,3,-17] [-18,7,6,19,-8,-4,-16,-1,13,-18,8,8,-16,17,-9,14,-2,-12,7,6] -> [20,15,20,19,-8,-4,20,15,17,20,17,17,20,17,-6,14,15,-6,15,20]

```

# Answer
> 6 votes
## JavaScript (ES6), ~~100~~ ~~90~~ ~~110~~ ~~102~~ 96 bytes

```
a=>b=>a.map(v=>t[v],a.map((_,k)=>a.map((x,i)=>t[x]=t[y=b[i]]=Math.max(k?t[x]:x,k?t[y]:y)),t={}))

```

My initial solution was 90 bytes:

```
a=>b=>a.map(v=>t[v],a.map(_=>a.map((x,i)=>t[x]=t[y=b[i]]=Math.max(t[x]||x,t[y]||y)),t={}))

```

Although it's passing all provided test cases, it fails for something such as:

```
A = [0, -1], B = [-1, -1]

```

### Test cases

```
let f =

a=>b=>a.map(v=>t[v],a.map((_,k)=>a.map((x,i)=>t[x]=t[y=b[i]]=Math.max(k?t[x]:x,k?t[y]:y)),t={}))

console.log(JSON.stringify(f([0])([0]))); // -> [0]
console.log(JSON.stringify(f([1])([2]))); // -> [2]
console.log(JSON.stringify(f([0,1,0])([2,1,0]))); // -> [2,1,2]
console.log(JSON.stringify(f([1,2,3])([0,0,1]))); // -> [3,3,3]
console.log(JSON.stringify(f([0,1,0,2])([-1,1,2,2]))); // -> [2,1,2,2]
console.log(JSON.stringify(f([1,0,1,-4])([-3,-1,-2,2]))); // -> [1,0,1,2]
console.log(JSON.stringify(f([1,2,3,-2])([1,0,-3,-2]))); // -> [1,2,3,-2]
console.log(JSON.stringify(f([-3,-2,-1,0,1])([-1,-1,-1,-1,-1]))); // -> [1,1,1,1,1]
console.log(JSON.stringify(f([-3,-2,-1,0,1])([2,-1,0,1,-3]))); // -> [2,2,2,2,2]
console.log(JSON.stringify(f([-3,5,5,3,1])([4,2,3,1,2]))); // -> [4,5,5,5,5]
console.log(JSON.stringify(f([4,0,2,-5,0])([0,4,-5,3,5]))); // -> [5,5,3,3,5]
console.log(JSON.stringify(f([-2,4,-2,3,2,4,1,1])([-2,4,1,2,2,3,1,-2]))); // -> [1,4,1,4,4,4,1,1]
console.log(JSON.stringify(f([-10,-20,-11,12,-18,14,-8,-1,-14,15,-17,18,18,-6,3,1,15,-15,-19,-19])([-13,6,-4,3,19,1,-10,-15,-15,11,6,9,-11,18,6,6,-5,-15,7,-11]))); // -> [-8,14,18,14,19,14,-8,-1,-1,15,14,18,18,18,14,14,15,-1,18,18]
console.log(JSON.stringify(f([20,15,2,4,-10,-4,-19,15,-5,2,13,-3,-18,-5,-6,0,3,-6,3,-17])([-18,7,6,19,-8,-4,-16,-1,13,-18,8,8,-16,17,-9,14,-2,-12,7,6]))); // -> [20,15,20,19,-8,-4,20,15,17,20,17,17,20,17,-6,14,15,-6,15,20]
console.log(JSON.stringify(f([0,-1])([-1,-1]))); // -> [0,0]
```

# Answer
> 5 votes
## CJam, 27 bytes

```
l~_])\z_,*f{{_2$&,*|}/:e>}p

```

Try it online! Test suite.

### Explanation

```
l~       e# Read and evaluate input, dumping arrays A and B on the stack.
_        e# Copy B.
])\      e# Wrap in array, pull off B, swap. Gives B [A B] on the stack.
z        e# Transpose the [A B] matrix to get a list of all equivalent pairs.
_,*      e# Repeat this list by the number of pairs. This is to ensure that the
         e# following procedure is applied often enough to allow transitive
         e# equivalences to propagate.
f{       e# Map this block over B, passing in the list of pairs each time...
  {      e#   For each pair...
    _2$  e#     Copy both the pair and the current value/list.
    &,   e#     Get the length of their intersection. If this is non-zero,
         e#     the current pair belongs to the current equivalence class.
    *    e#     Repeat the pair that many times.
    |    e#     Set union between the current value/list and the repeated pair.
         e#     This adds the pair to the current list iff that list already
         e#     contains one value from the pair.
  }/
  :e>    e#   Get the maximum value of this equivalence class.
}
p        e# Pretty print.

```

# Answer
> 4 votes
## Python 2, 91 bytes

```
f=lambda a,b:[a<x>b.update(b&set(x)and x)and b or max(f(zip(a,b)*len(a),{x})[0])for x in a]

```

# Answer
> 4 votes
## Python, 86 bytes

```
f=lambda a,b:a*(a==b)or f(*[map({x:y for x,y in zip(a,b)if x<y}.get,x,x)for x in b,a])

```

Simultaneously updates both lists by replacing each value in the first list by the corresponding element in the second list if it's greater. The replacement is done with `map` on a dictionary's `get` method. Then, swaps the lists, and repeats until they are equal.

# Answer
> 2 votes
## Php, ~~266~~ ~~241~~ ~~213~~ 200 bytes

Solution:

```
function u($x,$y){foreach($x as$i=>$j){$k[$y[$i]][]=$j;$k[$j][]=$y[$i];}$h=function($c,&$w)use($k,&$h){$w[]=$c;foreach($k[$c]as$u)!in_array($u,$w)&&$h($u,$w);return max($w);};return array_map($h,$x);}

```

Usage: `u([1,2,3], [0,0,1]);` returns the desired array.

Not-so golfed:

```
function unify($x, $y)
{
    foreach($x as $i=>$j) {
        $k[$y[$i]][] = $j;
        $k[$j][] = $y[$i];
    }

    $h = function ($c, &$w=[]) use ($k, &$h) {
        $w[] = $c;
        foreach($k[$c] as $u)
            !in_array($u, $w) && $h($u, $w);
        return max($w);
    };

    return array_map($h, $x);
}

```

# Answer
> 2 votes
# Pyth, 13 bytes

```
eMumS{s@#dGGC

```

Try it online: Demonstration

### Explanation:

Start with each pair. Iteratively extend each pair (list) with overlapping lists, deduplicate the elements and sort. Stop once this process converges. Print the maximum of each list.

# Answer
> 2 votes
# Dyalog APL, ~~29~~ 28 bytes

`⌈/¨({∪¨,/∘.{⍵/⍨≢⍺∩⍵}⍨⍵}⍣≡,¨)`

Same idea as the Pyth solution.

# Answer
> 1 votes
# Mathematica, 56 bytes

```
#/.($|##->Max@##&@@@ConnectedComponents@Thread[#<->#2])&

```

# Answer
> 0 votes
# Python, 522 bytes

```
a = [-2,4,-2,3,2,4,1,1]
b = [-2,4,1,2,2,3,1,-2]
m = {}
visited = {}
for i in range(len(a)):
    if a[i] in m:
        if b[i] not in m[a[i]]:
            m[a[i]].append(b[i])
    else:
        l = []
        l.append(b[i])
        m[a[i]] = l
    if b[i] in m:
        if a[i] not in m[b[i]]:
            m[b[i]].append(a[i])
    else:
        l = []
        l.append(a[i])
        m[b[i]] = l

def dfs(v, maximum):
    if v > maximum:
        maximum = v
    visited[v] = True
    for n in m[v]:
        if not visited[n]:
            d = dfs(n, maximum)
            if d > v:
                maximum = d
    return maximum

result = []
for k in range(len(a)):
    for q in m:
        visited[q] = False
    result.append(max(dfs(a[k], a[k]), dfs(b[k], b[k])))

print(result)

```

**Explanation**

Make a table of values corresponding to each unique element in in both arrays (`a` and `b` in this case). For example if

```
a = [0,1,0]
b = [2,1,0]

```

then the table would be:

```
0:[0,2]
1:[1]
2:[0]

```

then apply depth first search, so, for example, assume I pick the leftmost element in `a` the value is then `0` and `0` has the equivalences: `0` and `2`. Since `0` has already been visited, go to `2`. 2 has the equivalences: `0`. So the best result for choosing the leftmost element in `a` is `2`. Here's the tree:

```
   0
 /   \
0     2
       \
        0

```

and you want to take the largest value in there, so the result is `2`.

# Answer
> 0 votes
# Java, ~~273~~ 263 bytes

```
interface Z{int z(int x);default Z g(int m,int n){return x->{for(int t;x!=(t=x==m?z(n):z(x));)x=t;return x;};}static void f(int[]a,int[]b){Z y=x->x;int i=0,v;for(int u:a){u=y.z(u);v=y.z(b[i++]);if(u<v)y=y.g(u,v);if(v<u)y=y.g(v,u);}i=0;for(int u:a)a[i++]=y.z(u);}}

```

The method `f(int[]a,int[]b)` solves the challenge.

```
interface Z{

  //should return an "equivalent" integer
  int z(int x);

  //return a Z lambda where the 1st arg is "equivalent" to the 2nd arg
  default Z g(int m,int n){
    return x->{
      for(int t;x!=(t=x==m?z(n):z(x));) //always find the last equivalent number for x
        x=t;
      return x;
    };
  }

  //solve the challenge
  static void f(int[]a,int[]b){
    Z y=x->x; //start off with all numbers only equivalent only to themselves
    int i=0,v;
    for(int u:a){
      u=y.z(u); //get a's element's equivalent number
      v=y.z(b[i++]); //get b's element's equivalent number
      if(u<v)y=y.g(u,v); //if a's was smaller than b's, make a's equivalent to b's
      if(v<u)y=y.g(v,u); //if b's was smaller than a's, make b's equivalent to a's
    }
    i=0;
    for(int u:a) //overwrite a with each element's equivalent value
      a[i++]=y.z(u);
  }

}

```

First go through both arrays and keep track of equivalent numbers. Then modify every element in the first array to have the equivalent numbers stored.

# Answer
> 0 votes
# PHP, 132 bytes

```
function(&$a,$b){for(;$i<count($a);$i++){$r=$a[$i];$s=$b[$i];$r<$c[$s]?:$c[$s]=$r;$s<$c[$r]?:$c[$r]=$s;}foreach($a as&$v)$v=$c[$v];}

```

Anonymous function that takes two arrays.

This is my take on 'modify one of the arrays in place', as specified in the output of the challenge. This loops through each of the two arrays, records the equivalence if the current one is bigger than the one stored, then loops through the first array and replaces all the values with their largest equivalents. The first array is taken by reference (hence the `&$a`), so the array passed in is modified 'in place'.

# Answer
> 0 votes
# Java, 170 bytes

## Golfed

```
(a,b)->{int[]d=a.clone();for(int i=0,y;i<d.length;i++){y=0;for(int j=0;j<a.length;j++)if(a[j]==d[i]||b[j]==d[i])y=Integer.max(y,Integer.max(a[j],b[j]));d[i]=y;}return d;}

```

## Ungolfed

```
(a, b) -> {                                        // Two argument lambda
    int[] d = a.clone();                           // We clone our first array for modification
    for (int i = 0,y; i < d.length; i++) {         // Going through the elements of d...
        y = 0;                                     // We initialize our 'highest' equivalent
        for (int j = 0; j < a.length; j++) {       // Going through each of our arrays (a and b)...
            if (a[j] == d[i] || b[j] == d[i]) {    // If either of them is the number we're trying to match for equivalence...
                y = Integer.max(y, Integer.max(a[j], b[j])); // We see if the new number is bigger than the largest we've found.
            }
        }
        d[i] = y;                                  // We then assign the largest equivalent number for the current position in our output array.
    }
    return d; // And return!
}

```

Anonymous function that takes two `int[]`s as arguments and returns an `int[]`.

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


title: Print a Singing Angel

text:
# Question
Title: Print a Singing Angel
Keeping with a festive theme, print a carol singing angel with the shortest possible code. The angel is raising money for the homeless, so must be able to sing all three of the below songs available at request. To illustrate she can sing them, the title of the song must be placed within the speech bubble. This song title will be input by the user. Examples include:

* Mother Mary
* Jingle Bells
* Silent Night

**Input:**

Title: 1 of the 3 songs.

**Output:**

```
                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /              \
(           )  <
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

```

Please paste the result of your singing angel along with the song: "Silent Night".

**Speech Bubble Rules:**

The speech bubble must always have a frame of 12 underscore lines long.

The title of the song must always start on the second line.

The title of the song must always start 3 underscore spaces inside the bubble.

```
                  123456789...
(\   ___   /)    /            \
( \ (‘o‘) / )   /    Song      \
(           )  <     Title
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

```

Examples below:

```
                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /    Mother    \
(           )  <     Mary
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /    Jingle    \
(           )  <     Bells
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /    Silent    \
(           )  <     Night
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

```

# Answer
# PHP, 215 bytes

```
<?=($p=str_pad)($p($s=" ".$t="   ",18),30,_),$p("
(\   ___$t/)$s/",31),$p("\
( \ (‘o‘) / )$t/$t$argv[1]",37),"\
($s$s$t)  <$s$argv[2]",$p("
 (  ‘> <’  )$s\\",36),$p("/
$s/$s\\$s$t\\",32,_),"/
$t/$t$t\
  ‘ – “ - ‘";

```

takes title from first two command line arguments.

For Windows: add 1 to all pad-lengths after the first line, or duplicate backslashes before line breaks and replace all line breaks with `\n`
> 1 votes

# Answer
# JS (ES6), 328 330 bytes

```
a=(b,c)=>b.repeat(c);f=prompt().split(" ");if(f[1].length<5)f[1]+=" ";console.log(a(" ",18)+a("_",12)+`
(\\   ___   /)    /`+a(" ",12)+`\\
( \\ (‘o‘) / )   /    `+f[0]+`    \\
(`+a(" ",11)+`)  <     `+f[1]+a(" ",21)+`
 (  ‘> <’  )    \\`+a(" ",14)+`/
    /    \\       \\`+a("_",12)+`/
   /      \\
  ‘ – “ - ‘`)
```
* 1 helper function (a gets charcode (one char shorter) and repeats c times)
* 1 variable for getting input via `prompt()` and doing a split to array
* arguably abuses the special cases there but still does the job
* I assumed the extra 21 spaces in the middle column were needed

```
a=(b,c)=>b.repeat(c);f=prompt().split(" ");if(f[1].length<5)f[1]+=" ";console.log(a(" ",18)+a("_",12)+`
(\\   ___   /)    /`+a(" ",12)+`\\
( \\ (‘o‘) / )   /    `+f[0]+`    \\
(`+a(" ",11)+`)  <     `+f[1]+a(" ",21)+`
 (  ‘> <’  )    \\`+a(" ",14)+`/
    /    \\       \\`+a("_",12)+`/
   /      \\
  ‘ – “ - ‘`)
```
> 3 votes

# Answer
## Python 3.5, 207 chars, 226 bytes

```
def f(s):a,b=s.split();u='_'*12;[print(' '*int(x)if x.isdigit()else x,end='')for x in"99"+u+"\n(\\3___3/)4/66\\\n( \\ (‘o‘) / )3/4"+a+"4\\\n(92)2<5"+b+"\n (2‘> <’2)4\\95/\n4/4\\7\\"+u+"/\n3/6\\\n2‘ – “ - ‘"]

```

Output:

```
                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /    Jingle    \
(           )  <     Bells
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

```

Slightly ungolfed:

```
def angel(s):
    a, b = s.split()
    u = '_' * 12;
    out = "99" + u + "\n"
    out += "(\\3___3/)4/66\\\n"
    out += "( \\ (‘o‘) / )3/4" + a + "4\\\n"
    out += "(92)2<5" + b + "\n"
    out += " (2‘> <’2)4\\95/\n"
    out += "4/4\\7\\" + u + "/\n"
    out += "3/6\\\n"
    out += "2‘ – “ - ‘"
    [print(' '*int(x) if x.isdigit() else x, end='') for x in out]

```

It replaces numerical digits with the same number of spaces.
> 3 votes

# Answer
# Python 3.6 \- ~~286~~ 241 ~~224~~ bytes

```
def x(L):X,Y=L.split();E,D=' '*11,'_'*12;print(f"""{' '*18}{D}
(\   ___   /)    /{E} \\
( \ (‘o‘) / )   /    {X+' '*(10-len(X))}\\
({E})  <     {Y}
 (  ‘> <’  )    \{E}   /
    /    \       \{D}/
   /      \
  ‘ – “ - ‘""")

```

```
Input:
x("Silent Night")

```

```
Output:
                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /    Silent    \
(           )  <     Night
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

```

**Note** \- The version is `3.6` where string literal formatting was introduced. Hence, this won't work in earlier versions.
> 2 votes

# Answer
### Perl 6, 234 bytes (218 characters)

```
{"{' 'x 18}{'_'x 12}
(\\   ___   /)    /{' 'x 12}\\
( \\ (‘o‘) / )   /    {.words[0].fmt('%-9s')} \\
({' 'x 11})  <     {.words[1]}
(  ‘> <’  )    \\{' 'x 14}/
    /    \\       \\{'_'x 12}/
  /      \\
  ‘ – “ - ‘"}

```

A lambda that inputs the song name as a string, and outputs the snow angle as a string.

* Assumes that trailing spaces are not required.
* Bytes count is for UTF8 encoding, because that's how Perl 6 expects source code.
> 1 votes

# Answer
# Python 2.6, 391 bytes

```
def angel(a):
    X,Y=a.split()
    print("                  ____________")
    print"(\   ___   /)    /            \\"
    print"( \ (‘o‘) / )   /  ",  X,  "    \\"
    print"(           )  <   ", Y,        "  "
    print" (  ‘> <’  )    \              /"
    print"    /    \       \____________/"
    print("   /      \  ")
    print"  ‘ –

```

**Test Case:**

```
angel("Silent Night")
                  ____________
(\   ___   /)    /            \
( \ (‘o‘) / )   /   Silent     \
(           )  <    Night
 (  ‘> <’  )    \              /
    /    \       \____________/
   /      \
  ‘ – “ - ‘

```
> 1 votes

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


# Question
Title: Check if rectangles fill a rectangular space without gaps or overlaps
This challenge is based on another similar challenge. Because finding the most efficient packing of rectangles is NP-hard (that is, its solution is easy to check but hard to find), this challenge is a lot easier than this one here

## This Challenge

Given a bunch of rectangles, figure out whether or not they fill a rectangular space with no gaps or overlaps.

## Input

Input can be in two forms, one of which carries a scoring penalty.

The first: it contains a list of sublists, each with length 4. This list contains 4 integers which are the coordinates of opposite vertexes. Since all rectangles will be horizontal/vertical, there is no ambiguity as to where the rectangle is. Each sublist will contain four integers, which, in order, are the x-coordinate of the first vertex, the y-coordinate of the first vertex, the x-coordinate of the second vertex, and the y-coordinate of the second vertex.

The second: it contains four lists of integers with the same length. The four lists represent the different coordinates. If you imagine input option 1 as a matrix, the input here is just the transpose of the matrix. This input carries a `+20%` byte penalty.

## Output

Simple truthy/falsy output.

## Specifications

If there is a rectangle with area 0 (that is, `x1 == x2 || y1 == y2`), disregard this rectangle (so `[0 0 1 1], [2 2 3 2]` is valid). This specification is in place to make it harder for people to simply get the min/max x/y values.

`x1 <= x2` and `y1 <= y2` are not always true. If `x1 > x2 || y1 > y2`, the rectangle is not a zero-area rectangle; rather, it occupies the rectangular space between `(x1, y1)` and `(x2, y2)`.
Coordinates can be negative, in which case they still occupy the space between the coordinates.
The top-left-most rectangle is not always at `(0, 0)`; thus, the rectangular space that is filled doesn't necessarily have its top-left corner at `(0, 0)`.
(Thanks to @xnor for pointing out these ambiguities)

Please specify how you want your input and how your output will be represented.

## Scoring

Score is the size of the code in bytes, plus a byte penalty if applicable. Lowest score as of December 15th wins.

## Test Cases

```
0 0 1 2
1 0 3 1 ==> true
1 1 3 2

0 0 2 2
0 0 1 1 ==> false
0 0 0 0

0 0 1 1
2 2 2 2 ==> true
0 1 2 1

```

Good luck, happy golfing!

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

```
with(Math)a=>!(a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b]).filter(g=([l,t,r,b])=>(r-l)*(b-t))).reduce((s,b)=>s-g(b),g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))

```

Note: To use this, either evaluate it as a string and assign the result to a variable, or insert the assignment after the `with(Math)`. Explanation:

`with(Math)a=>!(` Bring `min` and `max` into scope.
`a=a.map(([l,t,r,b])=>[l<r?l:r,t<b?t:b,l>r?l:r,t>b?t:b])` Normalise the coordinates
`.filter(g=([l,t,r,b])=>(r-l)*(b-t)))` Remove empty rectangles, also defining a function to calculate area
`.reduce((s,b)=>s-g(b),` Subtract the areas of all the rectangles
`g([min,min,max,max].map((f,i)=>f(...a.map(a=>a[i])))))` from the area of the bounding box
`>a.some(([l,t,r,b],i)=>a.some(([m,u,s,c],j)=>i!=j&l<s&m<r&t<c&u<b))` and check that no rectangles overlap.

# Answer
> 0 votes
# Mathematica, 194 bytes

```
(r=Select[#,(#-#3)(#2-#4)&@@#>0&];m={#~Min~#3,#2~Min~#4,#~Max~#3,#2~Max~#4}&@@Transpose@r;b=Boole[(x-#)(x-#3)<0&&(y-#2)(y-#4)<0]&;Integrate[(Plus@@(b@@@r)-b@@m)^2,{x,#,#3}&@@m,{y,#2,#4}&@@m]<1)&

```

An ungolfed version:

```
1  (r = Select[#1, (#1 - #3) (#2 - #4) & @@ #1 > 0 &];
2   m = {Min[#1, #3], Min[#2, #4], Max[#1, #3], Max[#2, #4]} & @@ Transpose[r];
3   b = Boole[(x - #1) (x - #3) < 0 && (y - #2) (y - #4) < 0] &;
4   Integrate[
5     (Plus @@ (b @@@ r) - b @@ m)^2 ,
6     {x, #1, #3} & @@ m ,
7     {y, #2, #4} & @@ m
8   ] < 1
9  ) &

```

Line 1 defines `r` to be the set of nontrivial rectangles from the given input. (There's a lot of `& @@` going on in this code; that's just so we can use `#1,#2,#3,#4` for the four elements of a list instead of `#[[1]],#[[2]],#[[3]],#[[4]]`.) Then line 2 defines `m` to be the coordinates of the smallest rectangle bounding all of the ones listed in `r`; so if the input rectangles tile a large rectangle, that large rectangle must be `m`.

Line 3 defines function `b` which, when applied to a quadruple representing a rectangle, produces a function of two variables `x` and `y` that equals 1 if the point `(x,y)` is inside the rectangle and 0 if it's not. Line 5 produces many of these functions, one for each rectangle in `r` (all added together) and one last one for the large rectangle `m` (subtracted); that complicated two-variable function is then squared.

The key, at this point, is that that two-variable function is identically 0 if the small rectangles tile the large rectangle, but it will have some positive values if two small rectangles overlap, or some negative values (before squaring) if some part of the large rectangle isn't covered. We detect this by literally integrating(!) the two-variable function over the large rectangle (the limits of integration are given in lines 6-7): if we obtain 0, then the tiling was perfect, and if we obtain a positive value, then there was a problem somewhere. Since everything in sight is an integer, we save one final byte by using `< 1` instead of `== 0` in line 8.

(I think it's pretty fun that we can exploit Mathematica's ability to do calculus to solve this combinatorial problem.)

---
Tags: code-golf, math, array, geometry, decision-problem
---


# Question
Title: Swap out some periodic and non-periodic parts
In the decimal representation of every rational number `p/q`, you have a periodic tail, a non-periodic head, and a section before the decimal point in the following format:

```
(before decimal point).(non-periodic)(periodic)

```

Some examples include:

```
1/70 = 0.0142857... = (0).(0)(142857)
10/7 = 1.428571... = (1).()(428571)            ## no non-periodic part
1/13 = 0.076923... = (0).()(076923)
3/40 = 0.075 = (0).(075)()                    ## no periodic part
-2/15 = -0.13... = -(0).(1)(3)                ## negative
75/38 = 1.9736842105263157894... = (1).(9)(736842105263157894)
                                              ## periodic part longer than float can handle
25/168 = 0.148809523... = (0).(148)(809523)
120/99 = 40/33 = 1.212121... = (1).()(21)
2/1 = 2 = (2).()()                            ## no periodic, no non-periodic
0/1 = 0 = (0).()()
0/2 = 0 = (0).()()
299/792 = 0.37752... = (0).(377)(52)
95/-14 = -6.7857142... = -(6).(7)(857142)
-95/-14 = 6.7857142... = (6).(7)(857142)

```

The challenge is to swap the periodic and non-periodic parts, leaving the `before decimal point` alone, to create a new number. For example:

```
25/168 = 0.148809523... = (0).(148)(809523)
       => (0).(809523)(148) = 0.809523148148... = 870397/1080000

```

If a number has no periodic part like `0.25` turn that number into a new periodic number, and vice versa.

```
1/4 = 0.25 = (0).(25)() => (0).()(25) = 0.252525... = 25/99
4/9 = 0.444444... = (0).()(4) => (0).(4)() = 0.4 = 2/5
5/1 = 5 = (5).()() => (5).()() = 5 = 5/1

```

**The challenge**

* Take a fraction `x` as input, as a string, two inputs, a rational number, or whatever method suits your language.
* **Swap** the periodic and non-periodic parts of the decimal representation of `x` to create a new number, leaving the part before the decimal alone. The periodic part always starts as soon as possible so that the non-periodic part is as short as possible. Examples are below.
* Return the swapped number as a new fraction. The input is not necessarily reduced though the output should be. Input format is allowed to differ from output format.
* The numerator `p` of `x` will be an integer with absolute value of one million or less and the denominator `q` of `x` will be a **non-zero** integer with absolute value of one million or less.
* The numerator `r` and denominator `s` of the result is not guaranteed to be less than one million. Given the length of the periodic parts of these numbers, it is recommended that you avoid directly converting to floats.
* This is code golf. Shortest answer in bytes wins.

**Examples**

```
1/70 = (0).(0)(142857)     => (0).(142857)(0) = (0).(142857)() = 0.142857 = 142857/1000000
10/7 = (1).()(428571)      => (1).(428571)() = 1.428571 = 1428571/1000000
1/13 = (0).()(076923)      => (0).(076923)() = 0.076293 = 76923/1000000
3/40 = (0).(075)()         => (0).()(075) = 0.075075... = 75/999 = 25/333
-2/15 = -(0).(1)(3)        => -(0).(3)(1) = -0.311111... = -28/90 = -14/45
75/38 = (1).(9)(736842105263157894)
      => (1).(736842105263157894)(9) = (1).(736842105263157895)()  ## since 0.999... = 1
      = 1.736842105263157895 = 1736842105263157895/1000000000000000000
      = 347368421052631579/200000000000000000
25/168 = (0).(148)(809523) => (0).(809523)(148) = 0.809523148148... = 870397/1080000
120/99 = (1).()(21)        => (1).(21)() = 1.21 = 121/100
2/1 = (2).()()             => (2).()() = 2 = 2/1
0/1 = (0).()()             => (0).()() = 0 = 0/1
0/2 = (0).()()             => (0).()() = 0 = 0/1
299/792 = (0).(377)(52)    => (0).(52)(377) = 0.52377377... = 2093/3996
95/-14 = -(6).(7)(857142)  => -(6).(857142)(7) = -6.857142777... = -12342857/1800000
-95/-14 = (6).(7)(857142)  => (6).(857142)(7) = 6.857142777... = 12342857/1800000

```

# Answer
# Python 2, 292 bytes

```
def x(n,d):
 L=len;s=cmp(n*d,0);n*=s;b=p=`n/d`;a={};n%=d
 while not n in a:
  a[n]=p;q=n/d;n=n%d
  if q==0:n*=10;p+=' '
  p=p[:-1]+`q`
 p=p[L(a[n]):];a=a[n][L(b):]
 if n==0:p=''
 n=int(b+p+a);d=10**L(p+a)
 if a!='':n-=int(b+p);d-=10**L(p)
 import fractions as f;g=f.gcd(n,d);return(n/g*s,d/g)

```

Ungolfed version, works in both python 2&3. Also prints decimal representation.

```
def x(n,d):
# sign handling
 s=n*d>0-n*d<0
 n*=s
# b, a, p: BEFORE decimal, AFTER decimal, PERIODIC part
 b=p=str(n//d)
 a={}
 n%=d
# long division
 while not n in a:
  a[n]=p
  q=n//d
  n=n%d
  if q==0:
   n*=10
   p+=' '
  p=p[:-1]+str(q)
# a/p still contain b/ba as prefixes, remove them
 p=p[len(a[n]):]
 a=a[n][len(b):]
 if n==0: p=''
# print decimal representation
 print("(" + b + ").(" + a + ")(" + p + ")")
# reassemble fraction (with a and p exchanged)
 n=int(b+p+a)
 d=10**len(p+a)
 if a!='':
  n-=int(b+p)
  d-=10**len(p)
# reduce output
 from fractions import gcd
 g=gcd(n,d)
 return(n//g*s,d//g)

```
> 5 votes

# Answer
# Jelly, ~~102~~ ~~101~~ ~~89~~ ~~87~~ ~~83~~ ~~81~~ ~~79~~ ~~78~~ ~~77~~ 74 bytes

This took way to long to write, way too long to debug, and definitely needs a lot of golfing (~~eight seven six~~ ~~five~~ four links, holy cow), but it is, to the best of my knowledge, correct. Many, many thanks to Dennis for his help here, especially with the first two links. Many thanks to Rainer P. as well, as I ended up borrowing a lot of the algorithm in their Python answer.

**Golfing edits:** -1 byte thanks to Xanderhall. Bug fix from not using the correct logical NOT builtin. -13 bytes from golfing the numerator links. +1 byte from fixing a bug for negative `d` with thanks to Dennis. Restructured the links so that the numerator generation is all in one link. -2 bytes from combining the second and third links. -4 bytes from moving some common elements of the third and fourth links to the second link and the main link. -2 bytes from removing some superfluous chain operators. -2 bytes from rearranging the numerator link. -1 byte from moving `Ḣ€` to end of the second link. Fixed a bug in the main link. -1 byte from changing `Ṫ ... ,Ḣ` to `Ḣ ... ṭ`. -3 bytes from moving the numerator link into the main link.

Golfing suggestions welcome! Try it online!

```
2ị×⁵d⁴
ÇÐḶ,ÇÐĿḟ@\µḢḅÐfıṭµḢḊṭµḢ€€µF,ḢQ
ÇL€⁵*
×Ṡ©⁸×%µ³,⁴A:/;Ð€2ĿḌ×®,Ç_/€µ:g/

```

**Explanation**

First, I'll explain the **main link**, which calls the other links.

```
×Ṡ©⁸×%µ³,⁴A:/;Ð€2ĿḌ×®,Ç_/€µ:g/  Main link. Left argument: n (int), right argument: d (int)
                                Split into three chains.
×Ṡ©⁸×%  First chain
×       Multiply n by d.
 Ṡ©     Yield sign(n*d) and save it to the register.
   ⁸×   Multiply by n.
     %  Yield n*sgn(n*d) modulo d.

µ³,⁴A:/;Ð€2ĿḌ×®,Ç_/€  Second chain
                        What follows is the formula for the numerator.
                        (+) means combining the digits of two numbers into one number.
                        ( `integer (+) periodic (+) non-periodic` - `integer (+) periodic` )
µ                     Start a new monadic chain with n*sgn(n*d)%d.
 ³,⁴                  Pair the original two arguments as a nilad.
    A                 Get their absolute values.
     :/               Integer divide to get the integer part of abs(n)/abs(d).
          2Ŀ          Yield the results of the second link.
       ;Ð€            Append the integer part to each item in the right argument.
                        This appends to both lists from the second link.
            Ḍ         Convert each list from decimal to integer.
             ×®       Multiply by sign(n*d) retrieved from the register.
               ;Ç     Concatenate with the result of the third link (our new denominator).
                 _/€  Reduced subtract over each list.
                        Yields the proper numerator and denominator.

µ:g/  Third chain
µ     Start a new monadic chain with [numerator, denominator].
  g/  Yield gcd(numerator, denominator).
 :    Divide [numerator, denominator] by the gcd.
      Return this as our new fraction.

```

Then, the **first link** that gets the digits.

```
2ị×⁵d⁴  First link: Gets the decimal digits one at a time in the format:
          [digit, remainder to use in the next iteration]
2ị      Gets the second index (the remainder).
  ×⁵    Multiply by 10.
    d⁴  Divmod with d.

```

Now, the **second link** that gets the periodic and non-periodic parts of `n/d`, and a lot of other heavy lifting.

```
ÇÐḶ,ÇÐĿḟ@\µḢḅÐfıṭµḢḊṭµḢ€€µF,ḢQ  Second link: Loops the first link,
                                  separates the periodic digits and non-periodic digits,
                                  removes the extras to get only the decimal digits,
                                  and prepares for the third and fourth links.
                                Split into five chains.
ÇÐḶ,ÇÐĿḟ@\  First chain
ÇÐḶ         Loop and collect the intermediate results **in the loop**.
    ÇÐĿ     Loop and collect **all** of the intermediate results.
   ,        Pair into one list.
       ḟ@\  Filter the loop results out the list of all results,
              leaving only [[periodic part], [non-periodic part]].

µḢḅÐfıṭµḢḊṭ  Second and third chains
µ            Start a new monadic chain.
 Ḣ           Get the head [periodic part].
   Ðf        Filter out any [0, 0] lists from a non-periodic number,
  ḅ  ı        by converting to a complex number before filtering.
               Only removes 0+0j. This removes extra zeroes at the end.
      ṭ      Tack the result onto the left argument again.
       µ     Start a new monadic chain.
        Ḣ    Get the head [non-periodic and extra baggage].
         Ḋ   Dequeue the extra baggage.
          ṭ  Tack the result onto the left argument again.

µḢ€€µF,ḢQ  Fourth and fifth chains
µ          Start a new monadic chain with the processed periodic and non-periodic parts.
 Ḣ€€       Get the head of each list (the digits)
            in both the periodic and non-periodic parts.
    µ      Start a new monadic chain with these lists of digits.
     F     Left argument flattened.
       Ḣ   Head of the left argument.
      ,    Pair the flattened list and the head into one list.
        Q  Uniquify this list. (Only removes if non-periodic part is empty)
             Removes any duplicates resulting from a purely periodic n/d.

```

The **third link**, which yields our new denominator.

```
ÇL€⁵*  Third link: Generate the denominator.
         What follows is the formula for the denominator.
         ( 10**(num_digits) - ( 10**(num_periodic_digits) if len(non-periodic) else 0 ) )
Ç      Yield the results of the second link.
 L€    Get the length of each item in the list.
         The number of digits in total and the number of digits in the periodic part.
   ⁵*  10 to the power of each number of digits.

```
> 2 votes

---
Tags: code-golf, math, number, rational-numbers
---


# Question
Title: Find largest product of longest subsequence between min and max
# **Input:**

A non-empty sequence of integers greater than zero, the length of which is greater than 1.

# **Output:**

The largest product of all elements of the longest subsequence between the minimum and maximum elements of sequence including themselves.

## Note:

Because the minimum and maximum elements can be repeated, then to a definite answer necessary to find the longest possible subsequence, at one end of which is a minimum and at the other end maximum elements of the sequence. If there is multiple longest subsequences then choose subsequence with largest product.

# Examples:

## 1st example:

Input: `[5, 7, 3, 2, 1, 2, 2, 7, 5]`

Output: `42`

Explanation: `min == 1`, `max == 7`. There is 2 possible subsequences with min and max on ends: `[1, 2, 2, 7]` and `[7, 3, 2, 1]`. Their length is equal, so comparing products: `7*3*2*1 == 42` and `1*2*2*7 == 28`. Because `42 >= 28`, answer: `42`.

## 2nd example:

Input: `[1, 2, 2, 2, 4, 3, 3, 1]`

Output: `32`

Explanation: `min == 1`, `max == 4`. 2 subsequences: `[1, 2, 2, 2, 4]` and `[4, 3, 3, 1]`. Length of `[1, 2, 2, 2, 4]` is greater than length of `[4, 3, 3, 1]`. product: `1*2*2*2*4 == 32` =\> answer is `32`.

## 3d example:

Input: `[1, 2, 3, 4, 3, 3, 1]`

Output: `36`

Short explanation: `min == 1`, `max == 4`. 2 subsequences: `[1, 2, 3, 4]` and `[4, 3, 3, 1]`. `1*2*3*4 == 24`, `4*3*3*1 == 36`, `36 >= 24` =\> answer is `36`.

## 4th example:

Input: `[2, 2, 2]`

Output: `8`

Explanation: `min == 2`, `max == 2`. 2 different subsequences: `[2, 2]` and `[2, 2, 2]`. Length of `[2, 2, 2]` is greater than length of `[2, 2]`. product: `2*2*2 == 8` =\> answer is `8`.

## More *(random)* examples:

```
>>>[7, 2, 3, 6, 8, 6, 2, 5, 4, 3]
288
>>>[3, 3, 8, 9, 1, 7, 7, 2, 2, 4]
9
>>>[3, 2, 6, 5, 4, 1, 8, 8, 7, 9]
4032
>>>[7, 4, 2, 8, 8, 3, 9, 9, 5, 6]
31104

```

# Check your solution:

Here is Python 3 lambda *(788 bytes)*, which satisfies the requirement of the task:

```
lambda O: __import__('functools').reduce(__import__('operator').mul,O[[[slice(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1),slice(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1)][__import__('functools').reduce(__import__('operator').mul,O[O.index(min(O)):(len(O)-1-O[::-1].index(max(O)))+1],1)>=__import__('functools').reduce(__import__('operator').mul,O[O.index(max(O)):len(O)-1-O[::-1].index(min(O))+1],1)],slice(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1),slice(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1)][(len(range(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1))>len(range(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1)))-(len(range(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1))<len(range(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1)))]],1)

```

# Winner:

Shortest solution will win. All programming languages accepted.

*P.S.: I will be happy to the explanations of your solutions*

# Answer
# Jelly, 14 bytes

```
.ịạ/;L;P
ẆÇ€ṀṪ

```

Try it online!

### How it works

```
ẆÇ€ṀṪ     Main link. Argument: A (array)

Ẇ         Window; generate all substrings of A.
 Ç€       Map the helper link over the substrings.
   Ṁ      Take the maximum.
    Ṫ     Tail; select the last element.

.ịạ/;L;P  Helper link. Argument: S (array / substring)

.ị        At-index 0.5; select the last and first element of S.
  ạ/      Reduce by absolute difference.
    ;L    Append the length of S.
      ;P  Append the product of S.

```
> 5 votes

# Answer
# Jelly, 15 bytes

```
NMpMr/€LÐṀịµP€Ṁ

```

**TryItOnline!**

### How?

```
NMpMr/€LÐṀịµP€Ṁ - Main link: list of integers, L
           µ    - links to the left as a monadic chain with argument L
N               - negate elements of L
 M              - indexes of maximal elements (i.e. indexes of minimal elements of L)
   M            - indexes of maximal elements of L
  p             - Cartesian product of the min and max indexes
     /€         - reduce each list (all of which are pairs) with the dyad:
    r           -     range(a,b)  (note if a>b this is [a,a-1,...,b])
        ÐṀ      - filter keeping those with maximal
       L        -     length
          ị     - index into L (vectorises)   (get the values)
            P€  - product of a list for €ach
              Ṁ - maximum

```
> 6 votes

# Answer
# Perl 6, 108 bytes

```
{max ([*] $_ for .[.grep(+.max(+*)) with (for .min,.max,.max,.min {.first($^a,:k).. .first($^b,:k,:end)})])}

```
> 5 votes

# Answer
# R, 146 bytes

```
z=apply(expand.grid(which(max(x<-scan())==x),which(min(x)==x)),1,function(y)c(prod(x[y[1]:y[2]]),abs(diff(y))));max(z[1,which(z[2,]==max(z[2,]))])

```

Tricky challenge because of the length requirement. Also annoying because the would-be useful builtin `which.max` only returns the index of the first maximum it encounters, forcing me to use `which(max(x)==x)` instead... 3 times. Ohwell...

### Readable:

```
x <- scan()

maxs <- which(max(x)==x)
mins <- which(min(x)==x)
q <- expand.grid(maxs,mins)
z <- apply(q,1,function(y){
  c(prod(x[y[1]:y[2]]), abs(diff(y)))
  })

max(z[1, which(z[2, ]==max(z[2, ]))])

```
> 3 votes

# Answer
# PHP, ~~189~~ ~~173~~ 166 bytes

```
<?foreach($a=$_GET[a]as$p=>$b)foreach($a as$q=>$c)$b>min($a)|$c<max($a)?:$r[$d=abs($p-$q)+1]=array_product(array_slice($a,min($p,$q),$d));ksort($r);echo max(end($r));

```

similarly lazy but 33 bytes shorter (had to add 10 bytes to turn the snippet into a program):

1. Loop `$p/$b` and `$q/$c` through the array; if `$b==min` and `$c==max`,
add product of the sub-sequence to `$r[sub-sequence length]`
2. Sort `$r` by keys.
3. Print the max value of the last element.

Call in browser with array as GET parameter `a`.
Example: `script.php?a[]=5&a[]=7&a[]=3&a[]=2&a[]=1&a[]=2&a[]=2&a[]=7&a[]=5`
> 2 votes

# Answer
# Mathematica, 122 bytes

```
(g=#;Sort[{#.{-1,1},Times@@Take[g,#]}&/@Sort/@Join@@Outer[List,Sequence@@(Union@@Position[g,#@g]&/@{Max,Min})]][[-1,-1]])&

```

Surprised how long this turned out to be. First generates the Cartesian product of the appearances of the minima and maxima (as per Jonathan Allan's Jelly answer), then computes the lengths of those runs and their products, and selects the appropriate one by taking the last element of the sorted results.
> 2 votes

# Answer
# JavaScript, 187 bytes

```
f=
(l,M=Math,a=M.min(...l),z=M.max(...l),r=(m,n)=>[eval(l.slice(b=l.indexOf(m),c=l.lastIndexOf(n)+1).join`*`),M.abs(b-c)])=>(u=r(a,z),v=r(z,a),u[1]>v[1]?u[0]:v[1]>u[1]?v[0]:M.max(v[0],u[0]))

console.log([
  [5, 7, 3, 2, 1, 2, 2, 7, 5],
  [1, 2, 2, 2, 4, 3, 3, 1],
  [1, 2, 3, 4, 3, 3, 1],
  [2, 2, 2],
  [7, 2, 3, 6, 8, 6, 2, 5, 4, 3],
  [3, 3, 8, 9, 1, 7, 7, 2, 2, 4],
  [3, 2, 6, 5, 4, 1, 8, 8, 7, 9],
  [7, 4, 2, 8, 8, 3, 9, 9, 5, 6]
].map(a=>`[${a}] => ${f(a)}`).join`
`)
```
> 1 votes

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


title: Power modulo golf.

text:
# Question
Title: Power modulo golf.
Write a function f(a,b,c) that calculates a^b (mod c) in less than 10 seconds.

* a, b \< 10^100
* c \< 10000.

examples:

```
f(10^50, 10^50, 54123) = 46555
f(5^99, 10^99, 777) = 1

```

# Answer
## dc 1 or 5 chars

In GNU dc, there is the operator `|`, doing exactly this. Quoted from the manual:

> **`|`** Pops three values and computes a modular exponentiation. The first value popped is used as the reduction modulus; this value must be a non-zero number, and should be an integer. The second popped is used as the exponent; this value must be a non-negative number, and any fractional part of this exponent will be ignored. The third value popped is the base which gets exponentiated, which should be an integer. For small integers this is like the sequence Sm^Lm%, but, unlike ^, this command will work with arbitrarily large exponents.

You may assign it to "function" as following:

```
[|]sf

```

(also 5 chars...) This assigns `|` to `f`. You may call it like `lfx`.
> 3 votes

# Answer
# Python - 5 chars

```
f=pow

```

Test

```
>>> f(10**50, 10**50, 54123)
46555L
>>> f(5**99, 10**99, 777)
1L

```
> 2 votes

# Answer
## Haskell, 65

Takes the liberty of taking the modulus only on set bits of binary `b`, but given the range constraints that won't be a problem.

```
f a b c|b==0=1|odd b=mod(a*f a(b-1)c)c|0<1=f(mod(a^2)c)(div b 2)c

```
> 2 votes

# Answer
## Java 56 chars

My humble attempt with Java.

```
Object a(BigInteger...a){return a[0].modPow(a[1],a[2]);}

```

How to use :

```
a(new BigInteger("95"), new BigInteger("56"), new BigInteger("67"));

```
> 2 votes

# Answer
## Haskell (54)

```
f a=g a a
g d a b c|b>0=g(mod(d*a)c)a(b-1)c|True=mod d c

```

This is my algorithm:

1. let d = a
2. while b \> 0:
    * d \<- (d\*a)%c
    * b --
3. Return d%b
> 1 votes

# Answer
# Ruby, 15 bytes

```
->a,b,c{a**b%c}

```

Finishes in 0.114s for a=10, b=100, c=10000
> 1 votes

# Answer
Python 80 Characters

```
def f(a,b,c):
 x=1;y=a
 while b:
  if b%2:x=(x*y)%c
  y=(y*y)%c;b/=2
 return x%c

```
> 0 votes

# Answer
# PHP, 8 bytes

```
bcpowmod

```

You can assign the function name to a variable for 11 bytes:

```
$f=bcpowmod;

```

**Note:** `bcpowmod` requires libbcmath, which is built into PHP since version 4.0.4, but only enabled by default on Windows. On Linux you have to explicitly configure PHP with `--enable-bcmath`.
> 0 votes

---
Tags: code-golf, number
---


# Question
Title: Count the number of a number in the picture area
Your goal is to write a full program or function that takes 5 positive integers and a string with an image filename as input `[X1,Y1], [X2,Y2], N, image.jpg` in any reasonable format, where:

* First couple `[X1,Y1]` are the top left `X`,`Y` coordinates (`<=20`) of the blue rectangle area in the example picture (`16,11`).
* Second couple `[X2,Y2]` are the bottom right `X`,`Y` coordinates (`<=20`) of the blue rectangle area in the example picture (`20,22`).
* Fifth number `N` such `0 <= N <= 9` is the number that has to be found.
* Sixth parameter is a string with the filename of this JPG picture.

Output how many of `N`'s are present in the indicated area (outlined in blue in the picture for this example):

Click here to obtain a bigger clean version of the same image.

In the picture there are 500 numbers from `0` to `9` (included) arranged in 20 columnns per 25 rows, in monospaced `Courier New` font. Each different number has a different color (you can take advantage of this fact or ignore it and consider or convert the image in monocrome if that helps you).

**Test cases:**

```
[4,4],[13,5],1,image.jpg    > 4  (outlined in red)
[4,4],[13,5],4,image.jpg    > 2  (outlined in red)
[17,5],[17,5],2,image.jpg   > 1  (outlined in magenta)
[17,5],[17,5],9,image.jpg   > 0  (outlined in magenta)
[20,8],[20,9],3,image.jpg   > 1  (outlined in cyan)
[20,8],[20,9],2,image.jpg   > 0  (outlined in cyan)
[16,11],[20,22],0,image.jpg > 8  (outlined in blue)
[16,11],[20,22],3,image.jpg > 9  (outlined in blue)
[3,14],[11,20],7,image.jpg  > 6  (outlined in green)
[3,14],[11,20],5,image.jpg  > 6  (outlined in green)
[3,14],[11,20],8,image.jpg  > 8  (outlined in green)
[1,1],[20,25],0,image.jpg   > 47 (whole picture)
[1,1],[20,25],8,image.jpg   > 50 (whole picture)
[1,1],[20,25],1,image.jpg   > 55 (whole picture)

```

**Rules:**

* This is so the shortest code wins.
* You must take as input this JPG file.
* You are not allowed to hardcode the matrix of numbers represented in the JPG, or the results.
* Standard loopholes are forbidden.

# Answer
> 4 votes
# Mathematica, 92 bytes

```
Count[Take[Characters@StringSplit@TextRecognize@Binarize[Import@#4,.9],#2,#],ToString@#3,2]&

```

Unnamed function taking the arguments in this format: `[{X1,X2}, {Y1,Y2}, N, "image.jpg"]`. (Indeed, the fourth argument can be either the local file name or the URL `http://i67.tinypic.com/6qh5lj.jpg`.)

`Import@#4` imports the image file, `Binarize[...,.9]` darkens all of the numbers to black, and `TextRecognize` (the function clearly doing the heavy lifting here!) extracts a multi-line string from the resulting image, which is split into a nested list of characters with `Characters@`.

`Take[...,#2,#]` keeps only the characters corresponding to the outlined rectangle, and `Count[...,ToString@#3,2]` counts the number of occurrences of `N` in the result.

# Answer
> 2 votes
# Python 3 + pillow + pytesseract, 239 bytes

```
from PIL.Image import*
from pytesseract import*
def c(a,b,n,f):w,h=b[0]-a[0]+1,b[1]-a[1]+1;return len([1for i in range(h*w)if image_to_string(open(f).convert('L').point(lambda x:[9,0][x<250],'1')).split()[i//w+a[1]-1][i%w+a[0]-1]==str(n)])

```

This is horribly inefficient as for each number tile, the whole file is parsed. The much faster and slightly longer **243 bytes** solution would be

```
from PIL.Image import*
from pytesseract import*
def c(a,b,n,f):s=image_to_string(open(f).convert('L').point(lambda x:[9,0][x<250],'1')).split();w,h=b[0]-a[0]+1,b[1]-a[1]+1;return len([1for i in range(h*w)if s[i//w+a[1]-1][i%w+a[0]-1]==str(n)])

```

---
Tags: code-golf, number, image-processing
---


title: Number of prime knots with n crossings

text:
# Question
Title: Number of prime knots with n crossings
A prime knot is:

> a non-trivial knot which cannot be written as the knot sum of two non-trivial knots.

Explanation of a knot-sum: put the two knots adjacent,

... then draw two lines between them, to the same strand on each side, and remove the part between the lines you just drew. This composition of two knots will form a new, non-prime knot.

Here are all prime knots with 7 or fewer crossings (the Unknot is not prime):

You need to output the number of unique prime knots for a given number of crossings.

```
1   0
2   0
3   1
4   1
5   2
6   3
7   7
8   21
9   49
10  165
11  552
12  2176
13  9988
14  46972
15  253293
16  1388705

```

I don't think the values are known for inputs larger than `16`, but if given such an input, your code would need to find the correct result given enough time.

OEIS - A002863

# Answer
# Mathematica + KnotTheory\`, 13 bytes

```
NumberOfKnots

```

I didn't know this built-in function existed when I commented that the package might be useful. Everyone else had an equal chance to find it, since I commented about the library. I found it in the list of Lightly Documented Features. Still, I won't accept this answer, since I want to see answers by other people.
> 2 votes

---
Tags: code-golf, sequence, combinatorics, topology, knot-theory
---