# Question
Title: Is there an unmatched parenthesis in this String?
# Introduction

Given a String containing an arithmetic expression, your task is to output a truthy or falsey value based on whether it contains unmatched parentheses.

---

## Input

Your program should take in a String containing an arithmetic expression. It may take input in any way except assuming it to be present in a pre-defined variable. Reading from file, input box, modal dialog box etc. is fine. Taking input as function argument is allowed as well!

---

## Output

Your program should output a truthy or falsey value based on whether the input String contains any unmatched parentheses. It may output in any way except except writing to a variable. Writing to file, screen, console, terminal etc. is allowed. Outputting with function `return` is allowed as well!

---

## Rules

* For the purpose of this challenge, a parentheses is defined as any one of `[`, `{`, `(`, `)`, `}`, `]`. A parentheses is said to be unmatched if it does not have any corresponding opening/closing parentheses. For example, `[1+3` *does* contain unmatched parentheses.
* Ordering of parentheses does not matter in this challenge. So, `]1+3[` does not contain any unmatched parentheses. `{[)(}]` doesn't, as well.
* The input String will only contain following characters : `{`, `[`, `(`, `)`, `]`, `}`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`, `0`, `+`, `-`, `*`, `/` and `^`.
* Your program should output a truthy value if the input String contains an unmatched parentheses.
* Your program should output a falsey value if the input String does not contain an unmatched parentheses.
* You must specify the truthy and falsey values in your post.
* The input String will never be empty.
* If the input String does not contain any parentheses, your program should output falsey value.
* Standard loopholes apply.

---

## Test Cases

```
Input            ->            Output

"{"                            Truthy
"{{{{}}"                       Truthy
"{[]}"                         Falsey
"[]]["                         Falsey
")()()()("                     Falsey
"1+4"                          Falsey
"{)"                           Truthy
"([)]"                         Falsey
"(()"                          Truthy
"2*{10+4^3+(10+3)"             Truthy
"-6+[18-{4*(9-6)}/3]"          Falsey
"-6+[18-{4*)9-6](/3}"          Falsey

```

---

## Winning Criterion

This is , so the shortest code in bytes wins!

---

## Note

I'll be adding a similar challenge but in which *order will matter*, after some time! Stay Tuned!

# Answer
# 05AB1E, ~~14~~ 10 bytes

```
žuS¢2ô€ËP_

```

Try it online!

-4 thanks to Adnan.

`1` for truthy, `0` for falsey.

Its main power point is the `žu` builtin.

Explanation:

```
žuS¢2ô€ËP_
žu         Push '()<>[]{}'
  S        Split into individual chars
   ¢       Count occurrences of each char in the input. For <>, the count will always be 0
    2      Push 2
     ô     Split the array into pieces of that length, corresponding to respective matching brackets
      €    Map next command over the chunks
       Ë   Check if all elements are equal. If equal, it means that the corresponding bracket type is matched. <> will always be matched, since they will never occur in the input, so they'll both always have 0 occurrences
        P  Take the product of the boolean values. <> won't affect this, since it would always be 1
         _ Logically negate, convert 1 to 0 and non-1 (always 0 in this case) to 1

```
> 3 votes

# Answer
# Python 2, 47 bytes

```
lambda s:map(s.count,'([{')!=map(s.count,')]}')

```

Try it online! Test cases from musicman523.

Checks if list of counts for each type of open paren matches that for the corresponding close parens.

The program is one byte longer

```
q=input().count
print map(q,'([{')!=map(q,')]}')

```
> 4 votes

# Answer
# Python 2, 61 bytes

Saved 4 bytes thanks to WheatWizard!

```
lambda s:any(s.count(i)^s.count(j)for i,j in['{}','[]','()'])

```

Try it online!
> 2 votes

# Answer
# Jelly, 17 bytes

```
ċÐ€“[]{}()”s2E€ẠṆ

```

Try it online!

`1` is truthy, `0` is falsey.
> 1 votes

# Answer
# Python 3, ~~62~~ 61 bytes

Surprisingly pythonic for codegolf.

```
lambda x:all(x.count(y)-x.count(z)for y,z in("[]","()","{}"))

```

*-1 byte thanks to @musicman523*
> 1 votes

# Answer
# MATL, 15 bytes

```
!'[](){}'=sHeda

```

This outputs `1` if unmatched, `0` if matched.

**Try it online!**

### Explanation

```
!          % Implicitly input string. Tranpose into vertical vector of chars
'[](){}'   % Push this string
=          % Compare for equalty, with broadcast
s          % Sum of each column. This gives the count of each char of '[](){}'
He         % Reshape as a two-row column (in column-major order)
d          % Difference of the two entries of each column
a          % Any: gives true (1) if some entry is nonzero, false (0) otherwise
           % Implicitly display

```
> 1 votes

# Answer
# Javascript, 71 bytes:

```
x=>['()','[]','{}'].some(a=>x.split(a[0]).length!=x.split(a[1]).length)

```
> 1 votes

# Answer
# Ruby, 58+1 = 59 bytes

+1 byte for the `-n` flag.

```
f=->c{$_.count c}
p %w"() [] {}".any?{|s|f[s[0]]!=f[s[1]]}

```

Try it online!
> 1 votes

# Answer
## Javascript 57 bytes

```
x=>(g=z=>x.split(z).length,g`(`-g`)`|g`[`-g`]`|g`{`-g`}`)

```

Starting from asgallant's solution.

Matching returns 0. Non-matching returns non-zero.
> 1 votes

# Answer
# Python 2, 85 bytes

I can definitely golf this using subtraction instead but I'm running out of time. D:

```
lambda s,c=str.count:(c(s,'(')!=c(s,')'))or(c(s,'{')!=c(s,'}'))or(c(s,'[')!=c(s,']'))

```

Try it online!
> 0 votes

# Answer
## Retina, 26 bytes

```
O`.
+`\(\)|\[]|{}

[^*-9^]

```

Try it online!

### Explanation

```
O`.

```

Sort all characters so that corresponding brackets are adjacent (since neither `\` nor `|` can appear in the input).

```
+`\(\)|\[]|{}

```

Repeatedly remove pairs of matching brackets.

```
[^*-9^]

```

Try to match any remaining brackets (the regex matches anything that isn't a `^` or in the ASCII range from `*` to `9` which, among the valid input characters, are only the 6 brackets). If we find any, that means that there was an unmatched one. The result will be a positive integer if the input was unbalanced, `0` otherwise.
> 0 votes

# Answer
## PowerShell, 95 86 bytes

```
param($s)$h=@{};[char[]]$s|%{$h["$_"]++};$h.'['-$h.']'-or$h.'('-$h.')'-or$h.'{'-$h.'}'

```

Try it online!

Previous version

```
param($s)switch([char[]]$s){'('{$k++}')'{$k--}'['{$l++}']'{$l--}'{'{$m++}'}'{$m--}}$k-or$l-or$m

```

Try it online!
> 0 votes

# Answer
# Javascript, ~~149~~ 140 bytes

New solution incorporates bitwise operators (Thanks, arjun) and calculates if they are *not* equal, and uses or instead of and.

```
function f(x){return x.split("(").length!=x.split(")").length|x.split("{").length!=x.split("}").lengt|x.split("[").length!=x.split("]").length}

```

I don't yet have a snippet for this, so I'm not sure it works yet.

## OLD SOLUTION:

```
function f(x){return !(x.split("(").length==x.split(")").length&&x.split("{").length==x.split("}").length&&x.split("[").length==x.split("]").length)}

```

Checks if there are the same amount of one bracket and another, and then returns the opposite.

```
function f(x){return !(x.split("(").length==x.split(")").length&&x.split("{").length==x.split("}").length&&x.split("[").length==x.split("]").length)}

/*"{"                            Truthy
"{[]}"                         Falsey
"[]]["                         Falsey
")()()()("                     Falsey
"1+4"                          Falsey
"{)"                           Truthy
"([)]"                         Falsey
"2*{10+4^3+(10+3)"             Truthy
"-6+[18-{4*(9-6)}/3]"          Falsey
"-6+[18-{4*)9-6](/3}"          Falsey*/

console.log(f("{"));
console.log(f("{[]}"));
console.log(f("[]]["));
console.log(f(")()()()("));
console.log(f("1+4"));
console.log(f("{)"));
console.log(f("([)]"));
console.log(f("2*{10+4^3+(10+3)"));
console.log(f("-6+[18-{4*(9-6)}/3]"));
console.log(f("-6+[18-{4*)9-6](/3}"));
```
> 0 votes

# Answer
# C#, 87 bytes

```
using System.Linq;s=>s.Count(c=>c=='['|c=='{'|c=='(')==s.Count(c=>c==']'|c=='}'|c==')')

```

Pretty self explanatory, just test to see if the of left parenthesis equals the count of right parenthesis.
> 0 votes

# Answer
# Visual Basic.Net, ~~218~~ 192 Bytes

```
function t(m as string,v as string)
return Len(m)-Len(m.Replace(v,""))
end function
function b(q as String)
return not(t(q,"{")=t(q,"}")and t(q,"[")=t(q,"]")and t(q,"(")=t(q,")"))
end function

```
> 0 votes

# Answer
# PHP\>7.1, 124 Bytes

```
$t=!!$p=preg_replace("#[\d+/*^-]#","",$argn);for(;$p;$p=substr($p,1,-1))$t*=chr(($o=ord($p[0]))%5?$o+2:$o+1)==$p[-1];echo$t;

```

Instead of #`[\d+/*^-]` you can use `[^]{()}[]` or `[^\p{Pe}\p{Ps}]`

IntlChar::charMirror `IntlChar::charMirror($p[0])==$p[-1]` instead of `chr(($o=ord($p[0]))%5?$o+2:$o+1)==$p[-1]` checks not if the char is an openining or closing punctation so we can not use it without additional check `&$p[0]<$p[-1]` +8 Bytes

Online Version

# PHP, 151 bytes

A full Regex Solution

```
for($c=$t=!!$p=($r=preg_replace)("#[^]{()}[]#","",$argn);$p&&$c;)$p=$r(["#^{(.*)}$#","#^\[(.*)]$#","#^\((.*)\)$#"],[$a="$1",$a,$a],$p,1,$c);echo$t&!$p;

```

Try it online!
> 0 votes

# Answer
## Clojure, 65 bytes

```
 #(let[f(frequencies %)](some not(map =(map f"[{(")(map f"]})"))))

```

So long keywords :/ Returns `nil` for falsy and `true` for truthy.
> 0 votes

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


title: X marks the spot – a print job

text:
# Question
Title: X marks the spot – a print job
Given two numbers, print a page with an "X" in the specified location (±10%).

The numbers must be either percentages or fractions of the page's print area dimensions, e.g. `[25,75]` or `["15%","0%"]` or `[0.33,1]`. You do not have to consider margins. Just remember to state which number is width, and which is height, and which corner is the origin.

You may of course assume that a printer is connected, and any virtual printer counts too. In fact, you may want to set a PDF printer as your default printer before beginning this challenge.

You may create a printable file (e.g. a PDF) and send that to a virtual printer, which in turn creates your result PDF, but you may not directly create the final PDF. This has to be a proper print job.

If possible, please include a photo, scan, or screenshot of the result, or link to an online document. Note that Imgur accepts PDFs.

You will of course get more upvotes if you actually place an X rather than outputting newlines and spaces with an assumed font and paper size.

### Example

For input height 75% and width 25%, from top left, print the following document:

---

---

# Answer
# MacOS Bash + OfficeJet Pro 8600, 46

```
(yes ''|sed $[$2*3/5]q;printf %$[$1*4/5]sX)|lp

```

Origin is the top-left corner.

I did a test print to check the character dimensions of what gets printed by `lp` to my printer - it appears to be 82w x 64h, so (integer) multiplying percentages by 3/5 and 4/5 respectively gets within the 10% tolerance.

### Result, with command-line input of `25 75`:
> 5 votes

# Answer
# APL (Dyalog) on Windows, ~~36~~ 35 bytes

Anonymous function taking (Y,X) in percent from top left as argument

```
{'X.'⎕WC'Text'(2↓'X'⎕WC'Printer')⍵}

```

We begin with a list of three elements:

`{` an anonymous function (all variables are local)

the argument, e.g. `75 25`

`(` to the right of

`'X'⎕WC'Printer'`**W**indows **C**reate a Printer object named *X*, returning `'#.X'`

`2↓` drop two characters to get just `'X'`

`)` to the right of

`'Text'` what we will add

`'X.'⎕WC`**W**indows **C**reate a (type, content, position) object in the object *X*, returning `'#.X'`

`}` end of function (since *X* is local, it is destroyed when the function terminates, signalling to Windows that we are done with the print job, which causes Windows to print it)

---

##
> 1 votes

# Answer
# Java 8, ~~210~~ 209 bytes

*-1 byte: changed to currying syntax*

```
import java.awt.print.*;
x->y->{PrinterJob j=PrinterJob.getPrinterJob();j.setPrintable((g,p,i)->{g.drawString("X",(int)(p.getWidth()*x),(int)(p.getHeight()*y));return i;});try{j.print();}catch(Exception e){}};

```

Takes input as floating-point version of percent: `0.25, 0.75`.

### If paper size can be assumed as 8.5x11in (72dpi), 184 bytes

```
import java.awt.print.*;
x->y->{PrinterJob j=PrinterJob.getPrinterJob();j.setPrintable((g,p,i)->{g.drawString("X",x*612/100,y*792/100);return i;});try{j.print();}catch(Exception e){}};

```

Uses default values for printing to PDF. Now takes input as integer version of percent: `25, 75`.

### If a Windows OS can also be assumed, 177 bytes

```
import sun.awt.windows.*;
x->y->{WPrinterJob j=new WPrinterJob();j.setPrintable((g,p,i)->{g.drawString("X",x*612/100,y*792/100);return i;});try{j.print();}catch(Exception e){}};

```

Same inputs as above: `25, 75`.

## Usage

```
import java.awt.print.*;
...
Function<Double, Consumer<Double>> f =
x->y->{PrinterJob j=PrinterJob.getPrinterJob();j.setPrintable((g,p,i)->{g.drawString("X",(int)(p.getWidth()*x),(int)(p.getHeight()*y));return i;});try{j.print();}catch(Exception e){}};
...
f.apply(.25).accept(.75);

```

## Test Case

For input of `0.25, 0.75`:

(I don't have a physical printer, but this *should* still work without issue)
> 0 votes

# Answer
# C#, ~~259~~ ~~202~~ 201 bytes

```
namespace System.Drawing.Printing{w=>h=>{var p=new PrintDocument();p.PrintPage+=(s,e)=>e.Graphics.DrawString("X",new Font("Onyx",9),Brushes.Red,e.PageBounds.Width*w,e.PageBounds.Height*h);p.Print();};}

```

Onyx is a font installed on my Windows 10 machine by default where 4 seems to be the shortest font name. I tested that by running the following in C# and then inspecting `blah` in the debugger.

```
var blah = FontFamily.Families.GroupBy(o => o.Name.Length)
                              .OrderBy(g => g.Key);

```

Full/formatted version:

```
namespace System.Drawing.Printing
{
    class P
    {
        static void Main(string[] args)
        {
            Func<float, Action<float>> f = w => h =>
            {
                var p = new PrintDocument();
                p.PrintPage += (s, e) =>
                    e.Graphics.DrawString("X", new Font("Onyx", 9), Brushes.Red,
                                          e.PageBounds.Width * w, e.PageBounds.Height * h);
                p.Print();
            };

            f(0.25f)(0.75f);
        }
    }
}

```

Test case (0.25, 0.75):

---

##
> 0 votes

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


# Question
Title: Convert braces to Right Hand Brace (Sad Brace)
Right hand brace is a style of code bracketing in which curly braces and semicolons are all aligned to a single point on the right side of a a file.

Generally, this is considered bad practice, for several reasons.

## The Challenge

Take a multiline string through any method, and convert it's brace style to Right Hand Brace.

For this challenge, you only need it to work on Java code, however, it should theoretically work on any code that uses Braces and Semicolons.

You must grab all `{};` characters in a row, with any amount of whitespace between them. EG. `}}`, `; }` `}\n\t\t}`, and line them up on the right side of the file through the use of whitespace.

for example:

```
a {
b;
{c

```

should become

```
a {
b ;{
c

```

Or, more abstractly, push any and all whitespace from the left of all `{};` characters, to the right.

Indentation of lines should be otherwise preserved. Lines only containing whitespace after the movement of the `{};` characters may optionally be removed.

For example:

```
a{
    b{
        c;
    }
}
d;

```

May become either

```
a        {
    b    {
        c;}}
d        ;

```

or

```
a        {
    b    {
        c;}}

d        ;

```

Pushed to the right refers to all the `{};` characters being aligned to a point no shorter than the longest line. Any amount of space after that is acceptable.

So all the below is acceptable:

```
a {
bc;

a  {
bc ;

a   {
bc  ;

```

etc...

Lines in any code may contain `{};` characters between other non-whitspace characters, the handling of this case isn't necessary, although if you're inclined, you should leave them in place. Lines may also not contain any `{};` characters at all, and this should be handled correctly. As is shown below.

```
a {
b ;
c
d }

```

Because we don't want Code Review to see the horrible things we're doing, you need to make your code as small as possible.

## Examples / Testcases

**Generic Java**

```
public class HelloWorld{
       public static void main(String[] args){
           System.out.println("Hello, World!");
       }
}

```

becomes...

```
public class HelloWorld                        {
    public static void main(String[] args)     {
        System.out.println("Hello, World!")    ;}}

```

**The image itself**

```
public class Permuter{
    private static void permute(int n, char[] a){
        if (n == 0){
            System.out.println(String.valueOf(a));
        }else{
            for (int i=0; i<= n; i++){
                permute(n-1, a);
                swap(a, n % 2 == 0 ? i : 0, n);
            }
        }
    }
    private static void swap(char[] a, int i, int j){
        char saved = a[i];
        a[i] = a[j];
        a[j] = saved;
    }
}

```

becomes...

```
public class Permuter                                {
    private static void permute(int n, char[] a)     {
        if (n == 0)                                  {
            System.out.println(String.valueOf(a))    ;}
        else                                         {
            for (int i=0; i<= n; i++)                {
                permute(n-1, a)                      ;
                swap(a, n % 2 == 0 ? i : 0, n)       ;}}}
    private static void swap(char[] a, int i, int j) {
        char saved = a[i]                            ;
        a[i] = a[j]                                  ;
        a[j] = saved                                 ;}}

```

**Not so Perfectly Generic Python**

For contrast

```
def Main():
    print("Hello, World!");

Main();

```

becomes...

```
def Main():
    print("Hello, World!")    ;
Main()                        ;

```

## Notes

## Edit Notes

I reworded the challenge details, Hopefully I didn't break anyone's view of the rules, I assure you it was unintentional. This should be a much more clear and less self-conflicting spec.

# Answer
> 5 votes
# \+ Bash utilities, ~~64~~ ~~62~~ ~~61~~ ~~60~~ 62 bytes

*1 byte saved thanks to @DJMcMayhem for putting the ex commands together*

```
:se ve=all|%!wc -L
y$uò/^ *<93>[{};]
xk$pòò/<84> {};][{};]«$
lDî^R0|p

```

`^R` is the character literal for `<C-r>` (`0x12`) and `<84>` is `0x84` and `<94>` is `0x94`.

`wc -L` works on most \*nix based systems, but not macOS. For macOS, you have to do `gwc -L` after getting coreutils using brew, if you haven't already.

Try it online! (Java)

Try it online! (Python)

Try it online! (Java again)

This preserves all blank lines and does not handle tabs, only spaces.

Hexdump:

```
00000000: 3a73 6520 7665 3d61 6c6c 7c25 2177 6320  :se ve=all|%!wc
00000010: 2d4c 0a79 2475 f22f 5e20 2a93 5b7b 7d3b  -L.y$u./^ *.[{};
00000020: 5d0a 786b 2470 f2f2 2f84 207b 7d3b 5d5b  ].xk$p../. {};][
00000030: 7b7d 3b5d ab24 0a6c 44ee 1230 7c70       {};].$.lD..0|p

```

### Explanation

First we need to be able to move the cursor anywhere in the buffer, so we use

```
:se ve=all|...

```

and we chain this with another ex command using `|`

We need to get the length of the longest line in the input. This can be done with the shell command `wc -L`.

```
       ...|%!wc -L

```

This overwrites the current buffer (containing the input) with the result of `wc -L`. It gives an output of something like:

```
            42

```

and the cursor lands on the `4` in `42`. Then we copy this number by using `y$`: yank text from the cursor's position to the end of the line. This conveniently stores this number in register `0`. But more on that later. The input is replaced with this number, so to revert back, we `u`ndo.

Now say the input looked somewhat like this:

```
public class HelloWorld{
    public static void main(String[] args){
        System.out.println("Hello, World!");
    }
}

```

we need to move the braces `}` from the end of the buffer to just after the `println` statement.

```
ò                  " recursively do this until a breaking error:
 /^ *<93>[{};]     "   this compressed regex becomes /^ *\zs[{};]
                   "   this finds any character from `{};` after leading spaces
                   "   the cursor then goes to the `{};`

x                  "   delete character
 k$                "   go to the end of the line above
   p               "   and paste
    ò

```

If the regex cannot be found, a breaking error happens and breaks out of the recursion caused by `ò`.

Now comes the main part of this program, move all braces and semi-colons and align them as stated in the question.

```
ò                  " starts recursion
 /<84> {};][{};]«$ "   compressed form of [^ {};][{};]\+$
                   "   finds a sequence of `{};`s at the end of the line with a non-`{};` char to preceding it
 l                 "   move the cursor 1 to the right (since we were on the non-`{};` char now)
  D                "   delete everything from this position to the end of line
                   "   the deleted text contains `{};`
   î               "   execute as normal commands:
    ^R0            "   contains what's in register `0`, ie the length of the longest line
       |           "   now go to the column specified by that number
        p          "   and paste the contents
                   " implicit ending `ò`

```

Again, this recursion will be stopped by a breaking error caused when the regex could not be found in the buffer.

### Edits

* Used `D` instead of `d$` (I don't even know why I missed that in the first place)
* Compressed `[^` (in the regex) to `<84>`
* Fixed bug by using `\zs` (compressing it into `<93>`) and by removing the `$` in `$xk$pò`
* Removed useless newline
* Changed regex to make submission compliant with new rules and gained 2 bytes

# Answer
> 4 votes
# Ruby, ~~100~~ ~~114~~ 108 bytes

Reads file name as command line argument. If no file name is supplied, it'll read from STDIN. Does not handle tabs.

Try it online!

```
f=$<.read.gsub(/[\s;{}]*$/){$&.tr"
 ",''}
$><<f.gsub(/(.*?)([;{}]+)$/){$1.ljust(f.lines.map(&:size).max)+$2}

```

# Answer
> 3 votes
# Perl, 90 bytes

88 bytes of code + `-p0` flags.

```
\@a[y///c]for/.*/g;s/(.*?)\K[{};]$/$"x(@a-$1=~y%%%c).$&/gme;1while s/ *
 *([{};]+)$/$1/m

```

Try it online!

*Short explanations:*
`\@a[y///c]for/.*/g;` counts the length of the longest line: for each line, it defines the element at index `y///c` (ie the size of the line) of the array `@a`. At the end, the max index of `@a` (ie. the size of `@a`) is the size of the longest line.
`s/(.*?)\K[{};]$/$"x(@a-$1=~y%%%c).$&/gme` places the `{};` characters at the end of the lines.
`1while s/ *\n *([{};]+)$/$1/m` makes makes the braces on empty lines go on the line above.

Thanks to @primo from whom I partially "stole" the beginning of my code from here to count the length of the longest line.

# Answer
> 1 votes
# Python 2: 228 Bytes

```
import re
g=re.search
def b(a):
    s,l="",a.split('\n')
    r=max([len(k)for k in l])
    for k in l:
        n,m=g('[;}{]',k),g('[\w]',k)
        if n:n=n.start()
        if m:m=m.start()
        if n>m and m!=None:s+="\n"+k[:n]+" "*(r-n)
        s+=k[n:]
    print s

```

# Answer
> 1 votes
# stacked, 133 bytes

```
'\s+([;{}])' '$1'repl lines{!n'[\s;{}]+$'match''join:n\'$'+del\,}"!tr:$size"!$MAXmap@k{e i:e[' 'k i#rpad]"!}map tr[' 'join]map'
'join

```

Try it online!I could be heavily overthinking this... but whatevs. I'll look at it again tomorrow. Some nice tips:

1. `"!` can often be used in place of `map`, saving a byte or two, depending on if the next token starts with a word. However, it can only be used when each atom of the array is wanting to be mapped over. It's similar to a deep map.
2. A space is not needed after a quoted function, so `$MAXmap` is equivalent to `$MAX map`, which in turn is equivalent to `[MAX] map`. (Maps each array to its maximal element.)

# Answer
> 1 votes
## JavaScript (ES Proposal), ~~139~~ 121 bytes

```
f=
s=>s.replace(/^(.*?)\s*(([;{}]\s*)+)$/gm,(_,t,u)=>t.padEnd(Math.max(...s.split`
`.map(s=>s.length)))+u.replace(/\s/g,``))
```

```
<textarea rows=10 cols=40 oninput=o.textContent=f(this.value)></textarea><pre id=o>
```

Requires Firefox 48/Chrome 57/Opera 44/Safari 10/Edge 15 for `padEnd`. Edit: Saved 18 bytes thanks to @ValueInk.

# Answer
> 0 votes
# PHP, ~~201~~ ~~194~~ ~~185~~ ~~172~~ 167 bytes

```
foreach($f=file(f)as$s)$x=max($x,strlen($a[]=rtrim($s,"{} ;
")));foreach($a as$i=>$c)echo str_pad($c,""<$c|!$i?$x:0),trim(substr($f[$i],strlen($c))),"
"[""==$a[$i+1]];

```

takes input from file f; assumes single byte linebreaks and no tabs; preserves blank lines.

* +2 bytes for delimiting whitespace: append `+1` to the second `str_pad` parameter.
* -6 bytes if it was guaranteed that no code line consists of a single `0`:
Remove `""<` and replace `""==` with `!`.

**breakdown**

```
foreach($f=file(f)as$s)             // loop through file
    $x=max($x,strlen(                   // 3. set $x to maximum code length
        $a[]=                           // 2. append to array $a
            rtrim($s,"{} ;\n")          // 1. strip trailing whitespace and braces
    ));
foreach($a as$i=>$c)echo            // loop through $a
    str_pad($c,                         // 1. print code:
        !$i|""<$c                       // if first line or not empty
        ?$x                             // then padded to length $x
        :0                              // else unpadded (= print nothing)
    ),
    trim(substr($f[$i],strlen($c))),    // 2. print braces
    "\n"[""==$a[$i+1]]                  // 3. if next line has code, print newline
;

```

# Answer
> 0 votes
# Java 8, ~~312~~ 305 bytes

```
s->{String t="([;{}]+)",z[],r="",a;s=s.replaceAll(t+"[\\s\\n]*","$1").replaceAll(t,"$1\n");int m=0,l;for(String q:s.split("\n"))m=m>(l=q.length())?m:l;for(String q:s.split("\n")){z=q.split("((?<="+t+")|(?="+t+"))",2);for(a="",l=0;l++<m-z[0].length();a+=" ");r+=z[0]+a+(z.length>1?z[1]:"")+"\n";}return r;}

```

**Explanation:**

Try it here.

```
s->{                                  // Method with String parameter and String return-type
  String t="([;{}]+)",                //  Temp regex-String we use multiple times
    z[],a,                            //  Temp String-array and temp String
    r="";                             //  Result-String
  s=s.replaceAll(t+"[\\s\\n]*","$1")  //  We replace all ;{} in the input with zero or more whitespaces/newlines to just ;{}
     .replaceAll(t,"$1\n");           //  and then add a single newline after each group of ;{}
  int m=0,l;                          //  Two temp integers
  for(String q:s.split("\n"))         //  Loop (1) over the lines
    m=m>(l=q.length())?m:l;           //   To determine the longest line
                                      //  End of loop (1)
  for(String q:s.split("\n")){        //  Loop (2) over the lines again
    z=q.split("((?<="+t+")|(?="+t+"))",2);
                                      //   Split on groups of ;{}, but keep them in the array
    for(a="",l=0;l++<m-z[0].length();a+=" ");
                                      //   Amount of spaces we should add
    r+=z[0]+a+(z.length>1?z[1]:"")+"\n";
                                      //   Append this line to the result-String
  }                                   //  End of loop (2)
  return r;                           //  Return the result-String
}                                     // End of method

```

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


# Question
Title: XOR encrypt your programs with the source of other programs
Write two programs such that when the bytes of their source code are XOR-d together it produces a third, valid program, all in the same language. The length of each of the three programs in bytes must be identical.

The first program should output `A`. The second program should output `B`. The third program should output `C`.

A newline is optional, but if one outputs a newline, both of the others must too.

If you use any command line flags you must you the same ones for each program, i.e. all three programs must be executed the same way. If you're using a language like PHP that traditionally starts with the same combination of characters, e.g. `<?` but there is a command line option that drops those characters you may use that instead, i.e. PHP must only be run from the command line.

No input is allowed. Each program must be self-contained.

If your program is written entirely in ASCII the following tables might help:

```
Codes 0x20 - 0x3F
 !"#$%&'()*+,-./
0123456789:;<=>?

Codes 0x40 - 0x5F
@ABCDEFGHIJKLMNO
PQRSTUVWXYZ[\]^_

Codes 0x60 - 0x7E
`abcdefghijklmno
pqrstuvwxyz{|}~

```

### EDIT

Using non-printing characters **is allowed** as I didn't expressly forbid it originally. However, if you want to post a version that uses only printable characters as well that would be great! (Score whichever is the shortest.) The "clever factor" of using control codes has somewhat worn off now...

### END EDIT

XOR-ing any two codes from the same block will produce a code less than 0x20 which is therefore not a valid printable ASCII code, e.g. 0x41 (`A`) XOR 0x5A (`Z`) = 0x1B. XOR-ing any two codes from different blocks will produce a code from the third block, e.g. 0x61 (`a`) XOR 0x54 (`T`) = 0x35 (`5`).

```
    |  @` !Aa "Bb #Cc $Dd %Ee &Ff 'Gg (Hh )Ii *Jj +Kk ,Ll -Mm .Nn /Oo 0Pp 1Qq 2Rr 3Ss 4Tt 5Uu 6Vv 7Ww 8Xx 9Yy :Zz ;[{ <\| =]} >^~ ?_
--- + --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
 @` |  @` !Aa "Bb #Cc $Dd %Ee &Ff 'Gg (Hh )Ii *Jj +Kk ,Ll -Mm .Nn /Oo 0Pp 1Qq 2Rr 3Ss 4Tt 5Uu 6Vv 7Ww 8Xx 9Yy :Zz ;[{ <\| =]} >^~ ?_
!Aa | !Aa  @` #Cc "Bb %Ee $Dd 'Gg &Ff )Ii (Hh +Kk *Jj -Mm ,Ll /Oo .Nn 1Qq 0Pp 3Ss 2Rr 5Uu 4Tt 7Ww 6Vv 9Yy 8Xx ;[{ :Zz =]} <\| ?_ >^~
"Bb | "Bb #Cc  @` !Aa &Ff 'Gg $Dd %Ee *Jj +Kk (Hh )Ii .Nn /Oo ,Ll -Mm 2Rr 3Ss 0Pp 1Qq 6Vv 7Ww 4Tt 5Uu :Zz ;[{ 8Xx 9Yy >^~ ?_ <\| =]}
#Cc | #Cc "Bb !Aa  @` 'Gg &Ff %Ee $Dd +Kk *Jj )Ii (Hh /Oo .Nn -Mm ,Ll 3Ss 2Rr 1Qq 0Pp 7Ww 6Vv 5Uu 4Tt ;[{ :Zz 9Yy 8Xx ?_ >^~ =]} <\|
$Dd | $Dd %Ee &Ff 'Gg  @` !Aa "Bb #Cc ,Ll -Mm .Nn /Oo (Hh )Ii *Jj +Kk 4Tt 5Uu 6Vv 7Ww 0Pp 1Qq 2Rr 3Ss <\| =]} >^~ ?_ 8Xx 9Yy :Zz ;[{
%Ee | %Ee $Dd 'Gg &Ff !Aa  @` #Cc "Bb -Mm ,Ll /Oo .Nn )Ii (Hh +Kk *Jj 5Uu 4Tt 7Ww 6Vv 1Qq 0Pp 3Ss 2Rr =]} <\| ?_ >^~ 9Yy 8Xx ;[{ :Zz
&Ff | &Ff 'Gg $Dd %Ee "Bb #Cc  @` !Aa .Nn /Oo ,Ll -Mm *Jj +Kk (Hh )Ii 6Vv 7Ww 4Tt 5Uu 2Rr 3Ss 0Pp 1Qq >^~ ?_ <\| =]} :Zz ;[{ 8Xx 9Yy
'Gg | 'Gg &Ff %Ee $Dd #Cc "Bb !Aa  @` /Oo .Nn -Mm ,Ll +Kk *Jj )Ii (Hh 7Ww 6Vv 5Uu 4Tt 3Ss 2Rr 1Qq 0Pp ?_ >^~ =]} <\| ;[{ :Zz 9Yy 8Xx
(Hh | (Hh )Ii *Jj +Kk ,Ll -Mm .Nn /Oo  @` !Aa "Bb #Cc $Dd %Ee &Ff 'Gg 8Xx 9Yy :Zz ;[{ <\| =]} >^~ ?_ 0Pp 1Qq 2Rr 3Ss 4Tt 5Uu 6Vv 7Ww
)Ii | )Ii (Hh +Kk *Jj -Mm ,Ll /Oo .Nn !Aa  @` #Cc "Bb %Ee $Dd 'Gg &Ff 9Yy 8Xx ;[{ :Zz =]} <\| ?_ >^~ 1Qq 0Pp 3Ss 2Rr 5Uu 4Tt 7Ww 6Vv
*Jj | *Jj +Kk (Hh )Ii .Nn /Oo ,Ll -Mm "Bb #Cc  @` !Aa &Ff 'Gg $Dd %Ee :Zz ;[{ 8Xx 9Yy >^~ ?_ <\| =]} 2Rr 3Ss 0Pp 1Qq 6Vv 7Ww 4Tt 5Uu
+Kk | +Kk *Jj )Ii (Hh /Oo .Nn -Mm ,Ll #Cc "Bb !Aa  @` 'Gg &Ff %Ee $Dd ;[{ :Zz 9Yy 8Xx ?_ >^~ =]} <\| 3Ss 2Rr 1Qq 0Pp 7Ww 6Vv 5Uu 4Tt
,Ll | ,Ll -Mm .Nn /Oo (Hh )Ii *Jj +Kk $Dd %Ee &Ff 'Gg  @` !Aa "Bb #Cc <\| =]} >^~ ?_ 8Xx 9Yy :Zz ;[{ 4Tt 5Uu 6Vv 7Ww 0Pp 1Qq 2Rr 3Ss
-Mm | -Mm ,Ll /Oo .Nn )Ii (Hh +Kk *Jj %Ee $Dd 'Gg &Ff !Aa  @` #Cc "Bb =]} <\| ?_ >^~ 9Yy 8Xx ;[{ :Zz 5Uu 4Tt 7Ww 6Vv 1Qq 0Pp 3Ss 2Rr
.Nn | .Nn /Oo ,Ll -Mm *Jj +Kk (Hh )Ii &Ff 'Gg $Dd %Ee "Bb #Cc  @` !Aa >^~ ?_ <\| =]} :Zz ;[{ 8Xx 9Yy 6Vv 7Ww 4Tt 5Uu 2Rr 3Ss 0Pp 1Qq
/Oo | /Oo .Nn -Mm ,Ll +Kk *Jj )Ii (Hh 'Gg &Ff %Ee $Dd #Cc "Bb !Aa  @` ?_ >^~ =]} <\| ;[{ :Zz 9Yy 8Xx 7Ww 6Vv 5Uu 4Tt 3Ss 2Rr 1Qq 0Pp
0Pp | 0Pp 1Qq 2Rr 3Ss 4Tt 5Uu 6Vv 7Ww 8Xx 9Yy :Zz ;[{ <\| =]} >^~ ?_  @` !Aa "Bb #Cc $Dd %Ee &Ff 'Gg (Hh )Ii *Jj +Kk ,Ll -Mm .Nn /Oo
1Qq | 1Qq 0Pp 3Ss 2Rr 5Uu 4Tt 7Ww 6Vv 9Yy 8Xx ;[{ :Zz =]} <\| ?_ >^~ !Aa  @` #Cc "Bb %Ee $Dd 'Gg &Ff )Ii (Hh +Kk *Jj -Mm ,Ll /Oo .Nn
2Rr | 2Rr 3Ss 0Pp 1Qq 6Vv 7Ww 4Tt 5Uu :Zz ;[{ 8Xx 9Yy >^~ ?_ <\| =]} "Bb #Cc  @` !Aa &Ff 'Gg $Dd %Ee *Jj +Kk (Hh )Ii .Nn /Oo ,Ll -Mm
3Ss | 3Ss 2Rr 1Qq 0Pp 7Ww 6Vv 5Uu 4Tt ;[{ :Zz 9Yy 8Xx ?_ >^~ =]} <\| #Cc "Bb !Aa  @` 'Gg &Ff %Ee $Dd +Kk *Jj )Ii (Hh /Oo .Nn -Mm ,Ll
4Tt | 4Tt 5Uu 6Vv 7Ww 0Pp 1Qq 2Rr 3Ss <\| =]} >^~ ?_ 8Xx 9Yy :Zz ;[{ $Dd %Ee &Ff 'Gg  @` !Aa "Bb #Cc ,Ll -Mm .Nn /Oo (Hh )Ii *Jj +Kk
5Uu | 5Uu 4Tt 7Ww 6Vv 1Qq 0Pp 3Ss 2Rr =]} <\| ?_ >^~ 9Yy 8Xx ;[{ :Zz %Ee $Dd 'Gg &Ff !Aa  @` #Cc "Bb -Mm ,Ll /Oo .Nn )Ii (Hh +Kk *Jj
6Vv | 6Vv 7Ww 4Tt 5Uu 2Rr 3Ss 0Pp 1Qq >^~ ?_ <\| =]} :Zz ;[{ 8Xx 9Yy &Ff 'Gg $Dd %Ee "Bb #Cc  @` !Aa .Nn /Oo ,Ll -Mm *Jj +Kk (Hh )Ii
7Ww | 7Ww 6Vv 5Uu 4Tt 3Ss 2Rr 1Qq 0Pp ?_ >^~ =]} <\| ;[{ :Zz 9Yy 8Xx 'Gg &Ff %Ee $Dd #Cc "Bb !Aa  @` /Oo .Nn -Mm ,Ll +Kk *Jj )Ii (Hh
8Xx | 8Xx 9Yy :Zz ;[{ <\| =]} >^~ ?_ 0Pp 1Qq 2Rr 3Ss 4Tt 5Uu 6Vv 7Ww (Hh )Ii *Jj +Kk ,Ll -Mm .Nn /Oo  @` !Aa "Bb #Cc $Dd %Ee &Ff 'Gg
9Yy | 9Yy 8Xx ;[{ :Zz =]} <\| ?_ >^~ 1Qq 0Pp 3Ss 2Rr 5Uu 4Tt 7Ww 6Vv )Ii (Hh +Kk *Jj -Mm ,Ll /Oo .Nn !Aa  @` #Cc "Bb %Ee $Dd 'Gg &Ff
:Zz | :Zz ;[{ 8Xx 9Yy >^~ ?_ <\| =]} 2Rr 3Ss 0Pp 1Qq 6Vv 7Ww 4Tt 5Uu *Jj +Kk (Hh )Ii .Nn /Oo ,Ll -Mm "Bb #Cc  @` !Aa &Ff 'Gg $Dd %Ee
;[{ | ;[{ :Zz 9Yy 8Xx ?_ >^~ =]} <\| 3Ss 2Rr 1Qq 0Pp 7Ww 6Vv 5Uu 4Tt +Kk *Jj )Ii (Hh /Oo .Nn -Mm ,Ll #Cc "Bb !Aa  @` 'Gg &Ff %Ee $Dd
<\| | <\| =]} >^~ ?_ 8Xx 9Yy :Zz ;[{ 4Tt 5Uu 6Vv 7Ww 0Pp 1Qq 2Rr 3Ss ,Ll -Mm .Nn /Oo (Hh )Ii *Jj +Kk $Dd %Ee &Ff 'Gg  @` !Aa "Bb #Cc
=]} | =]} <\| ?_ >^~ 9Yy 8Xx ;[{ :Zz 5Uu 4Tt 7Ww 6Vv 1Qq 0Pp 3Ss 2Rr -Mm ,Ll /Oo .Nn )Ii (Hh +Kk *Jj %Ee $Dd 'Gg &Ff !Aa  @` #Cc "Bb
>^~ | >^~ ?_ <\| =]} :Zz ;[{ 8Xx 9Yy 6Vv 7Ww 4Tt 5Uu 2Rr 3Ss 0Pp 1Qq .Nn /Oo ,Ll -Mm *Jj +Kk (Hh )Ii &Ff 'Gg $Dd %Ee "Bb #Cc  @` !Aa
?_ | ?_ >^~ =]} <\| ;[{ :Zz 9Yy 8Xx 7Ww 6Vv 5Uu 4Tt 3Ss 2Rr 1Qq 0Pp /Oo .Nn -Mm ,Ll +Kk *Jj )Ii (Hh 'Gg &Ff %Ee $Dd #Cc "Bb !Aa  @`

```

Look up two characters from different columns and pick the character from their intersection that's in the other column, e.g. `B` and `e`: `"Bb` XOR `%Ee` is `'Gg`. `B` is second column and `e` is third column so pick the character from the first column in `'Gg`: `'`.

Example source:

```
 Ld+|?dpHs'-,pUe    (Program 1)
~bWn=n5Xe!t_G($3    (Program 2)
^.3EAQQ(-RSrkXqV    (Program 3)

```

Note that in each column there can only be one digit, one uppercase letter and one lowercase letter. For each column you may use any character you like in the first program, then your choice of 64 characters in the second program but only one possible character in the third program. 0x7F is not valid anywhere.

If you use Unicode it's up to you to validate the XOR-ing and you must say how it's encoded, e.g. UTF-8, UTF-16, etc. Each file must use the same encoding.

Score: Length of one program. Fewest bytes win!

# Answer
> 13 votes
# GolfScript, 6 bytes

A

```
A'AA'|

```

B

```
cdc"B"

```

C

```
"C"ce^

```

`|` and `^` are setwise or and xor with the empty input string, which would do nothing but remove duplicates in the string.

### Original version (with non-printable characters)

A

```
Xz'A'v

```

B

```
z9\x05"B"

```

C

```
"C"ceT

```

GolfScript ignores the undefined things, and the three programs are just `'A'` `"B"` `"C"`.

# Answer
> 11 votes
# Javascript, 23 bytes

Program A:

```
alert(' A '[~-~~2],'B')

```

Program B:

```
alert(FL$RSsYnYW1f='B')

```

Program C:

```
\0\0\0\0\0\0alert('C')\0;\0\0\03\0\0

```

You can test the conversion with the following function:

```
function xorString(a, b) {
  b = b || '';
  var length = Math.max(a.length, b.length);
  var chars = a.split('').map(function(charA, i) {
    var charB = b[i] || ' ';
    return String.fromCharCode(charA.charCodeAt(0) ^ charB.charCodeAt(0));
  });

  return chars.join('');
}

```

# Answer
> 3 votes
# PHP, 15+1 bytes

This one was ~~easy~~ **REALLY** harder than expected, but fun!
Sadly, this is the 3rd rewrite due to invalid answers.

This time, it is meant to run in the console (using the parameter `-r`).

**Program A:**

```
echo A;E925Z9A;

```

**Program B:**

```
echo B; zzzzzz;

```

**Result of XORing:**

```
\0\0\0\0\0\3\0eCHO C;\0 //base 64: AAAAAAADAGVDSE8gQzsA

```

Hex dump:

```
   |00|01|02|03|04|05|06|07|08|09|0A|0B|0C|0D|0E|0F|      TEXT
--------------------------------------------------------------------
00 |00|00|00|00|00|03|00|65|43|48|4F|20|43|3B|00|  |.......eCHO C;.
====================================================================

```

PHP will throw warnings about having the `\0` and `\3` chars before the echo, but that is ignorable.
It's just warnings!
It still runs and outputs the right answer!

---

Try running this, in your console:

```
php -r "@eval('echo B; zzzzzz;' ^ 'echo A;E925Z9A;');"

```

If you can't, try one of these:

If you still cant, run the code yourself:

```
<?php

error_reporting( 0 );

$program_a = 'echo A;E925Z9A;';

$program_b = 'echo B; zzzzzz;';

eval( $program_a );

eval( $program_b );

eval( $program_c = $program_a ^ $program_b );

echo PHP_EOL, 'a ^ b = ';

var_dump( $program_c );

```

---

## Old code, invalid:

**Program A:**

```
<?=A;zzzzz;

```

**Program B:**

```
<?=B;FEG9A;

```

**Result of XORing:**

```
\0\0\0\0<?=C;\0 //base64: AAAAAwA8Pz1DOwA=

```

# Answer
> 3 votes
# Pip, 4 bytes

Since user23013 is using non-printing ASCII in GolfScript, I figured I could do the same in Pip. It does require redirecting `stderr`, but that's okay, right?

**A**

```
??'A

```

where the two `?`s represent ASCII character 0.

**B**

```
'C'B

```

**C**

```
'C??

```

where the two `?`s represent ASCII characters 0 and 3, respectively.

Place each program in a file (`A.pip` for example). On Linux, do:

```
./pip.py A.pip 2>/dev/null

```

On Windows:

```
pip.py A.pip 2>nul

```

If error output is verboten, here's a 5-byte solution in printable ASCII:

```
pAa'A
 f"B"
P'Cec

```

# Answer
> 2 votes
# Microscript, 8 bytes each

A: `'APhgap)`

B: `'BPh@" A`

C: `<0><3><0><0>'CPh`

# Answer
> 2 votes
# Python, ~~19~~ ~~15~~ 14 bytes

a.py

```
00000000  70 72 69 6e 00 28 32 50  69 0a 74 22 41 22        |prin.(2Pi.t"A"|

```

b.py

```
00000000  70 72 69 6e 74 22 42 22  00 64 00 00 02 00        |print"B".d....|

```

c.py

```
00000000  00 00 00 00 74 0a 70 72  69 6e 74 22 43 22        |....t.print"C"|

```

I came up with this solution when I noticed that python (2.7.6 on Ubuntu 14.04) after seeing a NUL character will ignore the rest of that line.

Shortened by 1 bytes once I realized that the space after print wasn't needed. And shortened by 4 more bytes once I realized that the NUL character also cause the newline to be ignored so I can use it to break lines in the middle of a keyword.

# Answer
> 0 votes
# Chip, 8 bytes

All require the flag `-w`.

### Program A

```
a*gt*...

```

(`.` is the null character `\x00`)

### Program B

```
...*gb*t

```

(`.` is the null character `\x00`)

### Program C

```
a*g^Mb*t

```

Both A and B produce three warnings each (e.g.: `1:6 WARN: '' (0) is not a valid character`), but they can be safely ignored since they go to stderr. The elements `^` and `M` are valid, but do nothing here.

I'm fairly sure that this is the best that can be done with non-printables allowed. I'm not sure this proof is complete, but here goes:

A requires `a`, `g`, `t`, and some way to activate those elements (a minimum of two symbols are needed for this, and `*` is the simplest option here). Similarly,
B requires `b`, `g`, `t`, and two `*`s, and
C requires `a`, `b`, `g`, `t`, and two `*`s.

If C borrows its symbols directly from A and B, there will be two letters and two `*`s that remain unclaimed. (In my implementation, A's `t` and B's `g`). Those four elements can be overlapped so that they are mangled in C (producing `^` and `M` in this case). We now have those two mangled elements, plus the six required elements from above (C requires 6, the others only 5, but we need max() here), for a total of 8 elements.

---

## Chip (warning-free), 10 bytes

All require the flags `-wo`.

### Program A

```
a*HH^t*Gg

```

(there is a trailing space)

### Program B

```
KKb*t*^g G

```

### Program C

```
*a*b*^t Gg

```

This is provably the best we can do within printable ASCII, as follows: The three programs, combined, need a total of 2 `a`s, 2 `b`s, 3 `g`s, and 3 `t`s. Since none of these characters can transition to another, we need `2+2+3+3 = 10` separate positions.

---
Tags: code-golf, source-layout
---


title: Plus and Times, Ones and Nines

text:
# Question
Title: Plus and Times, Ones and Nines
Implement this recurrence relation as a function or program that inputs and outputs a non-negative integer:

* F(0) = 0
* F(N) = the smallest integer greater than F(N-1) such that the sum and/or product of its base-10 digits is N

N is your program's input and F(N) its output.

To be clear, the sum of the digits in a number like 913 is 9+1+3=13. The product is 9×1×3=27. For single-digit numbers, the sum and product is the same number. Numbers that contain a 0 of course have product 0.

The results through F(70) are:

```
N F(N)
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 19
11 29
12 34
13 49
14 59
15 69
16 79
17 89
18 92
19 199
20 225
21 317
22 499
23 599
24 614
25 799
26 899
27 913
28 1147
29 2999
30 3125
31 4999
32 5999
33 6999
34 7999
35 8999
36 9114
37 19999
38 29999
39 39999
40 41125
41 59999
42 61117
43 79999
44 89999
45 91115
46 199999
47 299999
48 311128
49 499999
50 511125
51 699999
52 799999
53 899999
54 911116
55 1999999
56 2111147
57 3999999
58 4999999
59 5999999
60 6111125
61 7999999
62 8999999
63 9111117
64 11111188
65 29999999
66 39999999
67 49999999
68 59999999
69 69999999
70 71111125

```

The shortest code in bytes wins. Kudos if you can show that your code takes advantage of some efficiency.

# Answer
> 4 votes
# 05AB1E, ~~20~~ 12 bytes

Saved 8 bytes thanks to *Osable*!

```
µNSDOsP‚¾>å½

```

Uses the **CP-1252** encoding. Try it online!

# Answer
> 3 votes
## Mathematica, 71 bytes, 68 characters

```
±0=0;±n_:=(For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];x)

```

For just 4 more bytes, here's a version that stores the values of `±n`:

```
±0=0;±n_:=(For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)

```

With the latter version, before you evaluate `±n`, `PlusMinus` will have two down values:

```
In[2]:= DownValues@PlusMinus
Out[2]= {HoldPattern[±0] :> 0, HoldPattern[±n_] :> (For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)}

```

Now if we evaluate `±20`:

```
In[3]:= ±20
In[3]:= 225

In[4]:= DownValues@PlusMinus
Out[4]= {HoldPattern[±0] :> 0, HoldPattern[±1] :> 1, HoldPattern[±2] :> 2, HoldPattern[±3] :> 3, HoldPattern[±4] :> 4, HoldPattern[±5] :> 5, HoldPattern[±6] :> 6, HoldPattern[±7] :> 7, HoldPattern[±8] :> 8, HoldPattern[±9] :> 9, HoldPattern[±10] :> 19, HoldPattern[±11] :> 29, HoldPattern[±12] :> 34, HoldPattern[±13] :> 49, HoldPattern[±14] :> 59, HoldPattern[±15] :> 69, HoldPattern[±16] :> 79, HoldPattern[±17] :> 89, HoldPattern[±18] :> 92, HoldPattern[±19] :> 199, HoldPattern[±20] :> 225, HoldPattern[±n_] :> (For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)}

```

This dramatically speeds up future calculations since Mathematica will no longer calculate the values between `0` and `20` recursively. The time saved is more dramatic as `n` increases:

```
In[5]:= Quit[]

In[1]:= ±0=0;±n_:=(For[x=±(n-1),FreeQ[{+##,1##}&@@IntegerDigits@x,n],x++];±n=x)

In[2]:= AbsoluteTiming[±60]
Out[2]= {23.0563, 6111125}

In[3]:= AbsoluteTiming[±60]
Out[3]= {9.89694*10^-6, 6111125}

```

# Answer
> 2 votes
# Pyth - ~~18~~ 17 bytes

*One byte saved thanks to @Jakube!*

Uses reduce to do the recursive thing.

```
uf}HsM*FBjT;hGSQZ

```

Test Suite.

# Answer
> 2 votes
# C#, ~~155~~ ~~159~~ 135 bytes

```
a=n=>{if(n<1)return 0;int i=n,s=0,p=1,N=a(n-1);for(;;){s=0;p=1;foreach(var c in++i+""){s+=c-48;p*=c-48;}if(i>N&(s==n|p==n))return i;}};

```

~~Super inefficient, takes a long time for just `N>=14`. Gonna try to get a more efficient, but longer solution.~~

Okay, much better now, but 4 bytes longer. Oh well, I can do `N<=50` pretty quickly now. Thank you @milk for saving 24 bytes!

# Answer
> 1 votes
# R, ~~124~~ 112 bytes

```
f=function(N){y=x=`if`(N-1,f(N-1),0);while(N!=prod(y)&N!=sum(y)){x=x+1;y=as.double(el(strsplit(c(x,""),"")))};x}

```

Fails at N=45 because R insists on writing 10.000 as 1e+05, which isnt appreciated by `as.numeric()`, this is fixable by using `as.integer()` at the cost of 12 bytes:

```
f=function(N){y=x=`if`(N-1,f(N-1),0);while(N!=prod(y)&N!=sum(y)){x=x+1;y=as.double(el(strsplit(c(as.integer(x),""),"")))};x}

```

As a statistical programming language R has annoyingly wordy ways of splitting numbers into a vector of digits. Especially because everything has to be converted back from strings to numerical values explicitly.

12 bytes saved thanks to billywob.

# Answer
> 1 votes
# JavaScript (ES6) ~~109~~ ~~107~~ ~~105~~ ~~91~~ 89 Bytes

```
f=n=>n&&eval(`for(i=f(n-1);++i,${x="[...i+''].reduce((r,v)=>"}+r+ +v)-n&&${x}r*v)-n;);i`)

console.log(f.toString().length + 2);
console.log(f(25));
console.log(f(13));
console.log(f(8));
```

# Answer
> 1 votes
# JavaScript (ES6), 84 ~~86~~

Edit: 2 bytes saved thx @Arnauld

```
f=n=>eval("for(v=n&&f(n-1),p=s=n+1;s&&p-1;)[...++v+''].map(d=>(p/=d,s-=d),p=s=n);v")

```

**Test** Note above 50 it will use too much of your CPU, click 'Hide results' to stop before it's too late

```
f=n=>eval("for(v=n&&f(n-1),p=s=n+1;s&&p-1;)[...++v+''].map(d=>(p/=d,s-=d),p=s=n);v")

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

i=0
step=_=>out(i+' '+f(i),++i,setTimeout(step,i*10))

step()
```

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

# Answer
> 1 votes
# Mathematica, 67 bytes

```
a@0=0;a@b_:=NestWhile[#+1&,a[b-1]+1,+##!=b&&1##!=b&@*IntegerDigits]

```

Function, named `a`. Takes a number as input and returns a number as output. Inspired by the previous Mathematica solution, but uses a different looping mechanism.

# Answer
> 1 votes
# C, 240 bytes

```
int f(char n){int q[19],i=19,r=n%9,j=9,*p=q,c=n/9;while(i)q[--i]=0;if(c){if(!r){r=9;c--;}q[9]=c;if(!(n%r)){n/=r;while((j-1)*(n-1)*c){if(n%j)j--;else{c--;q[9+j]++;n/=j;}}q[10]=c;if(1==n)p+=9;}while(++i<10){while(p[i]--)r=r*10+i;}}return(r);}

```

Trying to exploit some math properties of the sequence.

# Answer
> 0 votes
## PowerShell v3+, 114 bytes

```
param($n)$i=,0;$l=1;1..$n|%{for(;$_-notin((($b=[char[]]"$l")-join'+'|iex)),(($b-join'*'|iex))){$l++}$i+=$l};$i[$n]

```

Iterative solution, with no easy way to turn a number into the sum/product of its digits, so it's quite a bit longer than the JavaScript answers.

Takes input `$n`, sets `$i` to an array with just `0` (this is the collection of `F()`, and sets `$l` equal to `1` (this is the latest `F`). We then loop upward from `1` to `$n`, each iteration executing a `for` loop.

The `for` loop's conditional takes the `$l`atest number, in a string `"$l"`, then casts that as a `char`-array, and stores that array into temp variable `$b`. We then `-join` those digits together with `+` and pipe that to `iex` (short for `Invoke-Expression` and similar to `eval`). Additionally, we also do similar with `*`. Those two numbers are encapsulated in parens and treated as the array argument for the `-notin` operator against the current number `$_` of the outer loop (i.e., the `for` loop runs so long as either `+` and `*` are different than `$_`). The body of the `for` loop just increments `$l++`.

Once we're out of that inner `for` loop, we add our `$l` on as a new element of `$i`. Once we've fully completed the range loop, we just place `$i[$n]` on the pipeline, and output is implicit.

NB -- Gets pretty slow to execute above about `20`, simply because of the loop structure. For example, `N=40` takes about two minutes on my machine, and I've not even bothered testing `N>50`.

# Answer
> 0 votes
## Pyke, 17 bytes

```
t.fY'Bs]~ohR{Io(e

```

Try it here!

### Or 13 bytes noncompetitive

`first_n` now puts the amount of items already found plus one in `i` if used.

```
Q.fY'Bs]iR{)e

```

Try it here!

```
Q.f        )  -  first_n(input, start=1)
   Y          -   digits(^)
    'Bs]      -   [sum(^), product(^)]
         R}   -   V in ^
        i     -    len(results)+1
            e - ^[-1]

```

# Answer
> 0 votes
# Wonder, 49 bytes

```
f\.{0\0@(:>@(| =#1sum#0)=#1prod#0)(dp +1f -#0 1)N

```

Pattern matching ftw! Usage:

```
f\.{0\0@(:>@(| =#1sum#0)=#1prod#0)(dp +1f -#0 1)N}; f 10

```

More readable:

```
f\.{
  0\0
  @(
    find @(or = #1 sum #0) = #1 prod #0
  ) (dp + 1 (f -#0 1)) N
}

```

This is basically just a word-for-word implementation of the specs.

# Answer
> 0 votes
# Python 2, 77 bytes

```
f=lambda n,k=0,r=0:-(k>n)or-~f(n,k+(k in[eval(c.join(`r`))for c in'+*']),r+1)

```

Try it online!

# Answer
> 0 votes
# BASH, 107 bytes

## with fold + paste + bc

```
for ((;n<=$1;z++)){
p(){ fold -1<<<$z|paste -sd$1|bc;}
[ `p +` = $n -o `p \*` = $n ]&&((z-->n++))
}
echo $z

```

# Answer
> 0 votes
# Befunge, 101 bytes

```
&20p>:000pv
>\1+^vp011<
| >.@>:55+%:00g+00p10g*v>10g-*
::\$_^#!:/+55p01*!`"~":<^\-g00
< |!-g02
+1< v\

```

Try it online! But note that it's going to get really slow once you get into the high forties. If you want to test the full range, you really need to be using a Befunge compiler.

**Explanation**

```
&20p           Read N and save for later.

>              Start of main loop; current target and test number on stack, initially 0.
:              Duplicate the test number so we can manipulate it.
000p           Initialise the sum to 0.
110p           Initialise the product to 1.

>              Start of inner loop.
:55+%:         Modulo 10 of the test number to get the first digit.
00g+00p        Add to the sum.
10g*           Multiply by the product.
:"~"`!*        If greater than 126, set to 0 to prevent overflows - it'll never match.
10p            Update the product variable.
55+/           Divide the test number by 10 to get the next digit.
:!_            If not zero, repeat the inner loop

$              Drop the zero left over from the loop.
\::00g-\10g-   Compare the sum and product with the current target.
*|             Multiply the two diffs and branch; up if no match, down if either match.
\1+^           On no match, we increment the test number and repeat the main loop.
:>20g-!|       With a match, we compare the current target with the saved N.
1+\v           If that doesn't match, increment the current target and restart main loop.
\>.@           If it does match, we've got our result; output it and exit.

```

# Answer
> 0 votes
# PHP, 110 bytes

```
for(;$c<=$a=$argn;$c=count($r))array_product($s=str_split($n++))!=$c&&array_sum($s)!=$c?:$r[]=~-$n;echo$r[$a];

```

Try it online!

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


title: Explode the Box

text:
# Question
Title: Explode the Box
This is very similar to this challenge, "Implode the Box". It was a pretty nice challenge and it didn't get many answers, so I'm going to post a similar challenge (strongly) inspired by it.

ASCII Boxes look like this:

```
++    +---+    +------+           +---+    +---+
++    |   |    |      |           |   |    |   |
      |   |    |      |           |   |    |   |
+-+   |   |    |      |           |   |    |   |
+-+   |   |    |      |           |   |    +---+
      +---+    |      |           |   |
+--+           |      |           |   |    ++
|  |           |      |           |   |    ||
|  |           +------+           |   |    ||
+--+                              |   |    ||
                                  +---+    ||
                                           ||
                  +-----+                  ||
+------------+    |     |                  ++
|            |    |     |
|            |    |     |
+------------+    +-----+

```

Here are the same ASCII boxes, exploded:

```
                  --
        -        -  -               -        -
++    +- -+    +-    -+           +- -+    +- -+
++    |   |    |      |           |   |    |   |
     |     |  |        |         |     |  |     |
+-+  |     | |          |       |       |  |   |
+-+   |   | |            |     |         | +- -+
      +- -+  |          |     |           |  -
+--+    -     |        |       |         | ++
|  |           |      |         |       |  ||
|  |  --       +-    -+          |     |  |  |
+--+ -  -        -  -             |   |  |    |
    -    -        -- -            +- -+  |    |
   -      -         - -             -     |  |
  -        -      +-   -+                  ||
+-          -+    |     |                  ++
|            |   |       |
|            |    |     |
+-          -+    +-   -+
  -        -        - -
   -      -          -
    -    -
     -  -
      --

```

Here are the test cases in a more computer-friendly format.

The challenge is to take an ASCII box as input and output the exploded box. A box is exploded according to the following rules:

1. `+` never changes, and neither do the `-` and `|` immediately neighboring them.
2. Starting from the corners and moving in, each `-` and `|` move outward one more space than the previous one.

The result does not have to be symmetrical, so padding spaces are not needed.

1. Standard loopholes apply.
2. You can take input in any reasonable format, including LF/CR/CRLF separated lines, array of lines, array of array of characters, etc.
3. The only characters in the input string will be "+", "-", "|", " ", and "\n" (or whatever your newline is, if you choose this input format), and your output string should follow the same rules.
4. You may optionally have a single trailing newline at the end of the last line.
5. The smallest ASCII box you need to handle is the top-left example. Every ASCII box will have exactly 4 "+"s, exactly at its corners.
6. You can assume you will always get a single valid ASCII box as input.
7. The box must be left-aligned.
8. Each line may have trailing whitespace so long as the line (without the newline character) is not longer than the longest line with all trailing whitespace removed. That is, the padding whitespace to the right cannot stretch out farther than the center of the extrusion.

# Answer
> 4 votes
# Retina, 136 bytes

```
m`^
#
(¶#\|(.*))(?<=\1\1)(?=\1)
¶|  $2
T`#`_`^(.|¶#)*$
}T`#`p
+`^(.*?-)(-+)-
$.1$* $2¶$1$.2$* -
+`¶(.*?-)(-+)(-.*)$
¶$1$.2$* $3¶$.1$* $2

```

Try it online! Explanation:

```
m`^
#

```

Prefix a `#` to every line.

```
(¶#\|(.*))(?<=\1\1)(?=\1)
¶|  $2

```

Where there are three identical lines, i.e. in the middle of a box, expand the middle line of the three. (When there are more than tree identical lines, all except the first and last get expanded.)

```
T`#`_`^(.|¶#)*$

```

If no lines were expanded, then delete the `#`s again. This causes the loop to exit.

```
}T`#`p

```

If at least one line was expanded, change the `#`s to spaces, and continue the loop. (I use `p` here because it's easier to see.) At the end of the loop, the sides of the box will have been completely exploded.

```
+`^(.*?-)(-+)-
$.1$* $2¶$1$.2$* -

```

Repeatedly remove all but two of the top row of `-`s and put them on their own line preceding the rest of the original row. This explodes the top of the box.

```
+`¶(.*?-)(-+)(-.*)$
¶$1$.2$* $3¶$.1$* $2

```

Repeatedly remove all but two of the bottom row of `-`s and put them on their own line following the rest of the original row. This explodes the bottom of the box.

# Answer
> 2 votes
# Charcoal, ~~56~~ 49 bytes

```
ＳχＡ⁰δＷ¬⁼χＳＡ⁺¹δδ↓+Ｐ↗×-÷⁺¹Ｌχ²↙×|÷⁺¹δ²‖ＯＯ﹪Ｌχ²‖ＯＯ↓﹪δ²

```

Try it online! Link is to verbose version of code. Explanation: The input box is measured; `χ` contains the first line of the box, while `δ` contains the number of rows of the box. The top left corner of the exploded box is then drawn: first the `+`, then the `-`s, then the `|`s. Finally the box is reflected horizontally and vertically; for boxes of odd sizes, a 1-character overlap is taken into account.

# Answer
> 1 votes
# Jelly,  ~~80 79~~  77 bytes

```
HĊḢ
ċÐ€⁾-|HµHĊS+=0Ḣ$©Ṭ€ḤH⁸ÇR¤¦;€⁸Ço1¤¦3Ḋ€¹®?z0ZUŒḄm0$⁸ḂḢ¤?€ŒḄm0$⁸ḂṪ¤?ị“-|+ ”Y

```

A full program that prints the result.

**Try it online!**

### How?

```
HĊḢ - Link 1: first item halved and rounded up: list
H   - halve (vectorises)
 Ċ  - ceiling (vectorises) (i.e. round up)
  Ḣ - head

ċÐ€⁾-|HµHĊS+=0Ḣ$©Ṭ€ḤH⁸ÇR¤¦;€⁸Ço1¤¦3Ḋ€¹®?z0ZUŒḄm0$⁸ḂḢ¤?€ŒḄm0$⁸ḂṪ¤?ị“-|+ ”Y - Main link

breaking the Main link down:

ċÐ€⁾-|Hµ - get the dimensions: list of characters
   ⁾-|   - literal ['-', '|']
 Ð€      - map with:
ċ        - count - yields a list [number of '-'s, number of '|'s]
      H  - halve
       µ - start a new monadic link using that as it's argument, call it d

HĊS+=0Ḣ$©Ṭ€ - build an appropriately sized binary "diagonal":                  e.g. [3,4]
H           - halve (vectorises)                                                  [1.5,2]
 Ċ          - ceiling (vectorises) (rounds each halved dimension up)                [2,2]
  S         - sum                                                                       4
       $    - last two links as a monad:
    =0      -   equals zero? (vectorises)                                           [0,0]
      Ḣ     -   head (first element)  (i.e. "inputHasZeroDashes")                       0
        ©   - copy to register and yield
   +        - addition                                                                  4
         Ṭ€ - untruth for €ach                              [[1],[0,1],[0,0,1],[0,0,0,1]]

ḤH⁸ÇR¤¦ - make 1s become 2s for those that will represent '|' rather than '-'
Ḥ       - double (vectorises)                               [[2],[0,2],[0,0,2],[0,0,0,2]]
      ¦ - sparse application...
        - ... at indexes:
     ¤  -   nilad followed by link(s) as a nilad:
  ⁸     -     chain's left argument, d                                              [3,4]
   Ç    -     call last link (1) as a monad                                             2
    R   -     range                                                                 [1,2]
        - ...of:
 H      -   halve                                           [[1],[0,1],[0,0,2],[0,0,0,2]]

;€⁸Ço1¤¦3 - place a 3 where the `+` should be
        3 - literal 3                                                                   3
       ¦  - sparse application...
          - ... at indexes:
      ¤   -   nilad followed by link(s) as a nilad:
  ⁸       -     chain's left argument, d                                            [3,4]
   Ç      -     call last link (1) as a monad                                           2
     1    -     literal 1                                                               1
    o     -     logical or (when no '-' Ç returns 0, but we want 1)                     2
          - ...of:
;€        -   concatenate for €ach (append the 3)         [[1],[0,1,3],[0,0,2],[0,0,0,2]]

Ḋ€¹®? - a further correction for zero width edge-case
    ? - if:
   ®  -   recal from register (inputHasZeroDashes)
      - ...then:
Ḋ€    -   dequeue €ach (all rows were made one longer, so adjust)
      - ...else:
  ¹   -   identity (do nothing)                           [[1],[0,1,3],[0,0,2],[0,0,0,2]]

z0ZU - pad with zeros and reflect each
z0   - transpose with filler zero               [[1,0,0,0],[0,1,0,0],[0,3,2,0],[0,0,0,2]]
  Z  - transpose                                [[1,0,0,0],[0,1,3,0],[0,0,2,0],[0,0,0,2]]
   U - upend (reverse each)                     [[0,0,0,1],[0,3,1,0],[0,2,0,0],[2,0,0,0]]

ŒḄm0$⁸ḂḢ¤?€ - perform reflections of row elements
         ?€ - if for €ach:
        ¤   -   nilad followed by link(s) as a nilad:
     ⁸      -     chain's left argument, d                                          [3,4]
      Ḃ     -     modulo 2 (vectorises)                                             [1,0]
       Ḣ    -     head (first element)                                                  1
            - ...then:
ŒḄ          -   bounce  [[0,0,0,1,0,0,0],[0,3,1,0,1,3,0],[0,2,0,0,0,2,0],[2,0,0,0,0,0,2]]
            - else:
    $       -   last two links as a monad
  m0        -     reflect

ŒḄm0$⁸ḂṪ¤? - perform reflection of rows
         ? - if:
        ¤   -   nilad followed by link(s) as a nilad:
     ⁸      -     chain's left argument, d                                          [3,4]
      Ḃ     -     modulo 2 (vectorises)                                             [1,0]
       Ṫ    -     tail (last element)                                                   0
            - ...then:
ŒḄ          -   bounce
            - else:
    $       -   last two links as a monad
  m0        -     reflect
            -           [[0,0,0,1,0,0,0],[0,3,1,0,1,3,0],[0,2,0,0,0,2,0],[2,0,0,0,0,0,2],
            -            [2,0,0,0,0,0,2],[0,2,0,0,0,2,0],[0,3,1,0,1,3,0],[0,0,0,1,0,0,0]]

ị“-|+ ”Y - create the list of characters itself
 “-|+ ”  - literal ['-', '|', '+', ' ']
ị        - index into                           ["   -   "," +- -+ "," |   | ","|     |",
         -                                       "|     |"," |   | "," +- -+ ","   -   "]
       Y - join with newlines
         -       "   -   \n +- -+ \n |   | \n|     |\n|     |\n |   | \n +- -+ \n   -   "
         - implicit print:
           >>>   -
           >>> +- -+
           >>> |   |
           >>>|     |
           >>>|     |
           >>> |   |
           >>> +- -+
           >>>   -

```

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


title: Miller-Rabin Strong Pseudoprimes

text:
# Question
Title: Miller-Rabin Strong Pseudoprimes
Given a non-negative integer `N`, output the smallest odd positive integer that is a strong pseudoprime to all of the first `N` prime bases.

This is OEIS sequence A014233.

## Test Cases (one-indexed)

```
1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

```

Test cases for `N > 13` are not available because those values have not been found yet. If you manage to find the next term(s) in the sequence, be sure to submit it/them to OEIS!

## Rules

* You may choose to take `N` as a zero-indexed or a one-indexed value.
* It's acceptable for your solution to only work for the values representable within your language's integer range (so up to `N = 12` for unsigned 64-bit integers), but your solution must theoretically work for any input with the assumption that your language supports arbitrary-length integers.

---

## Background

Any positive even integer `x` can be written in the form `x = d*2^s` where `d` is odd. `d` and `s` can be computed by repeatedly dividing `n` by 2 until the quotient is no longer divisible by 2. `d` is that final quotient, and `s` is the number of times 2 divides `n`.

If a positive integer `n` is prime, then Fermat's little theorem states:

In any finite field `Z/pZ` (where `p` is some prime), the only square roots of `1` are `1` and `-1` (or, equivalently, `1` and `p-1`).

We can use these three facts to prove that one of the following two statements must be true for a prime `n` (where `d*2^s = n-1` and `r` is some integer in `[0, s)`):

The Miller-Rabin primality test operates by testing the contrapositive of the above claim: if there is a base `a` such that both of the above conditions are false, then `n` is not prime. That base `a` is called a *witness*.

Now, testing every base in `[1, n)` would be prohibitively expensive in computation time for large `n`. There is a probabilistic variant of the Miller-Rabin test that only tests some randomly-chosen bases in the finite field. However, it was discovered that testing only prime `a` bases is sufficient, and thus the test can be performed in an efficient and deterministic manner. In fact, not all of the prime bases need to be tested - only a certain number are required, and that number is dependent on the size of the value being tested for primality.

If an insufficient number of prime bases are tested, the test can produce false positives - odd composite integers where the test fails to prove their compositeness. Specifically, if a base `a` fails to prove the compositeness of an odd composite number, that number is called a *strong pseudoprime* to base `a`. This challenge is about finding the odd composite numbers who are strong psuedoprimes to all bases less than or equal to the `N`th prime number (which is equivalent to saying that they are strong pseudoprimes to all *prime* bases less than or equal to the `N`th prime number).

# Answer
# C, ~~349~~ ~~295~~ ~~277~~ ~~267~~ 255 bytes

```
N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

```

Takes 1-based input on stdin, e.g.:

```
echo "1" | ./millerRabin

```

---

It certainly isn't going to discover any new values in the sequence any time soon, but it gets the job done. UPDATE: now even slower!

* Slightly faster and shorter, with inspiration from Neil A's answer (`a^(d*2^r) == (a^d)^(2^r)`)
* Significantly slower again after realising that *all* solutions to this challenge will be odd, so there is no need to explicitly enforce that we only check odd numbers.
* Now using GCC's `__int128`, which is shorter than `unsigned long long` while also working with larger numbers! Also on little-endian machines, the printf with `%llu` still works fine.

### Less-minified

```
N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

```

### (Outdated) Breakdown

```
unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See https://codegolf.stackexchange.com/a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

```

---

As mentioned, this uses 1-based input. ~~But for n=0 it produces 9, which follows the related sequence https://oeis.org/A006945.~~ Not any more; now it hangs on 0.

Should work for all n (at least until the output reaches 2^64) but is incredibly slow. I have verified it on n=0, n=1 and (after a **lot** of waiting), n=2.
> 3 votes

# Answer
# Python 2, ~~633~~ ~~465~~ ~~435~~ ~~292~~ ~~282~~ ~~275~~ ~~256~~ 247 bytes

0-indexed

> Question your implementation and try something new

Converting from a function to a program saves some bytes somehow...

If Python 2 gives me a shorter way to do the same thing, I'm going to use Python 2. Division is by default integer, so an easier way to divide by 2, and `print` doesn't need parentheses.

```
n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

```

Try it online!

Python is notoriously slow compared to other languages.

Defines a trial division test for absolute correctness, then repeatedly applies the Miller-Rabin test until a pseudoprime is found.

Try it online!

**EDIT**: Finally golfed the answer

**EDIT**: Used `min` for the trial division primality test and changed it to a `lambda`. Less efficient, but shorter. Also couldn't help myself and used a couple of bitwise operators (no length difference). In theory it should work (slightly) faster.

**EDIT**: Thanks @Dave. My editor trolled me. I thought I was using tabs but it was being converted to 4 spaces instead. Also went through pretty much every single Python tip and applied it.

**EDIT**: Switched to 0-indexing, allows me to save a couple of bytes with generating the primes. Also rethought a couple of comparisons

**EDIT**: Used a variable to store the result of the tests instead of `for/else` statements.

**EDIT**: Moved the `lambda` inside the function to eliminate the need for a parameter.

**EDIT**: Converted to a program to save bytes

**EDIT**: Python 2 saves me bytes! Also I don't have to convert the input to `int`
> 3 votes

# Answer
# Perl + Math::Prime::Util, 81 + 27 = 108 bytes

```
1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

```

Run with `-lpMMath::Prime::Util=:all` (27-byte penalty, ouch).

## Explanation

It's not just Mathematica that has a builtin for basically anything. Perl has CPAN, one of the first large library repositories, and that has a huge collection of ready-made solutions for tasks like this one. Unfortunately, they aren't imported (or even installed) by default, meaning that it's basically never a good option to use them in , but when one of them happens to fit the problem perfectly…

We run through consecutive integers until we find one that's not prime, and yet a strong pseudoprime to all integer bases from 2 to the *n*th prime. The command-line option imports the library that contains the builtin in question, and also sets implicit input (to line-at-a-time; `Math::Prime::Util` has its own builtin bignum library that doesn't like newlines in its integers). This uses the standard Perl trick of using `$\` (output line separator) as a variable in order to reduce awkward parses and allow the output to be generated implicitly.

Note that we need to use `is_provable_prime` here to request a deterministic, rather than probabilistic, prime test. (Especially given that a probabilistic prime test is likely using Miller-Rabin in the first place, which we can't expect to give reliable results in this case!)

# Perl + Math::Prime::Util, 71 + 17 = 88 bytes, in collaboration with @Dada

```
1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..nth_prime$_}{

```

Run with `-lpMntheory=:all` (17 byte penalty).

This uses a few Perl golfing tricks that I either didn't know (apparently Math::Prime::Util has an abbreviation!), knew about but didn't think of using (`}{` to output `$\` implicitly once, rather than `"$_$\"` implicitly every line), or knew about but somehow managed to misapply (removing parentheses from function calls). Thanks to @Dada for pointing these out to me. Apart from that, it's identical.
> 2 votes

---
Tags: code-golf, sequence, number-theory, primes, integer
---


# Question
Title: Arranging arbitrary rectangles to fill a space
# Can these rectangles fill a rectangular space?

Given a bunch of rectangles, you are asked whether or not they can be arranged to fill a rectangular space.

## Specs

Given a bunch of arbitrary `m x n` rectangles; `0 <= m, n <= 1000`, determine whether or not it is possible to arrange them so that they cover exactly a rectangular area without any holes or overlaps. The rectangles cannot be rotated, and each rectangle may only be placed once.

## Input

The input for this is very flexible, as long as the input gives some sort of list of 2-space dimensions. For example, both of the following are valid:

### Separated by Space, Return

```
1 2
1 5
4 5
3 6

```

### List of Dimensions

`[[1, 2], [1, 5], [4, 5], [3, 6]]`

## Output

Any sort of true/false values like true/false, 0/1, T/F, True/False, etc. If you are going to use an output method that's not very obvious, please specify in your answer.

## Examples

### Test Case 1

Input:

```
1 1
1 5
2 6

```

Output: `true` (or something similar)
How to arrange it:

```
XYYYYY
ZZZZZZ
ZZZZZZ

```

### Test Case 2

Input:

```
1 1
2 2

```

Output: `false` (or something similar)
Explanation: It becomes obvious that you cannot arrange two squares of different sizes and get their edges to line up.

### Test Case 3

Input:

```
1 1
1 2
1 2
2 1
2 1

```

Output: `true` (or something similar) How to arrange it:

```
AAB
DEB
DCC

```

As @ETHProductions pointed out, for all of the other test cases, you can keep combining rectangles with a common edge length until you have only one rectangle, so this test case is just to break any code that uses this idea.

### Test Case 4

Input:

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

```

Output: `true` (or something similar)
How to arrange it:

```
AAABBBBEE
AAACCDDDD
FFFFFGGGH
FFFFFGGGH
IIIJJKKLH
IIIMMMMMH

```

**Note**: You do not need to state how to arrange it, you only need to determine whether not it can be arranged.

This is code golf, so the shortest answer in bytes wins! I will accept the shortest answer as of January 14th, but feel free to submit answers later than that since I can still give upvotes! :)

Happy golfing!

~ A.L.

P.S. If you know what tag should be applied to this problem, please add it, I have absolutely no idea what to put as a tag other than code-golf.

**EDIT**: Your program should be able to process up to 25 rectangles, in at most 10 seconds on a decent computer (I'll be quite flexible on this rule).

**EDIT**: I've extended the submission acceptance deadline to the last day of the year, but I doubt I'll get an answer by then...

**EDIT**: I've extended the submission acceptance deadline by 2 weeks, so if no more answers come in by then, the current C answer will be accepted! :)

# Answer
## C, 1135 ~~1158~~ ~~1231~~ ~~1598~~ bytes

Well, it's past the stated deadline, but seeing as how there are no answers yet, here's one (a bit long) in C.

**Returns:**

* 0 (zero) on failure (don't fit)
* Full fitting matrix on success

---

### Update:

Original code could get stuck on some matrices, taking much longer than the allowed 10s. Current revision should complete all matrices in under 1s. This is accomplished by 1) Sorting the input rectangles and 2) skipping repeated sizes when fitting.

### Golfed:

```
#define R r[i]
#define Z return
#define _(B,D,E) for(int B=E;B<D;B++)
struct{int x,y,u,p;}r[25],*S;int A,M,N,U,V,X,Y;char *P;T(x,y,w,h){_(I,x+w,x)_(J,y+h,y)if(I/U|J/V|P[J*U+I])Z 0;Z 1;}L(x,y,w,h,c){_(I,x+w,x)_(J,y+h,y)P[J*U+I]=c;}F(){int x=0,y;while(++x<A)if(!P[x])break;if(x/A){_(i,V,0)printf("%*.*s\n",U,U,P+i*U);exit(0);}y=x/U;x-=y*U;_(i,N,0)if(!R.u&T(x,y,R.x,R.y))R.u=1,L(x,y,R.x,R.y,'A'+i),F(),R.u=0,L(x,y,R.x,R.y,0);}O(i,y){if(!R.u){if(!T(0,y,R.x,R.y))Z;R.u=1;R.p=0;L(0,y,R.x,R.y,'A'+i);y+=R.y;}if(y-V||F())_(j,N,0)if(j-i&!r[j].u){O(j,y);while(r[j].x-r[j+1].x|r[j].y-r[j+1].y)j++;}R.u=0;L(R.p,(y-=R.y),R.x,R.y,0);}Q(i,x){if(!R.u){if(R.x>U-x)Z;R.u=1;R.p=x;L(x,0,R.x,R.y,'A'+i);x+=R.x;}if(x-U||O(i,1))_(j,N,0)if(j-i&!r[j].u)Q(j,x);L(x-=R.x,0,R.x,R.y,0);R.u=0;}C(int*a,int*b){Z*a-*b?*a-*b:a[1]-b[1];}main(){_(i,25,0)if(++N&scanf("%d%d\n",&R.x,&R.y)-2)break;_(i,N,0){A+=R.x*R.y;if(R.x>X)X=R.x;if(R.y>Y)Y=R.y;}_(i,A+1,1)if(!(A%i)){if(i<Y|A/i<X)continue;M++;S=realloc(S,M*16);S[M-1].y=i;S[M-1].x=A/i;}qsort(S,M,16,C);P=calloc(A+1,1);_(j,M,0){U=S[j].x;V=S[j].y;_(i,N,0)R.u=1,L(0,0,R.x,R.y,'A'+i),Q(i,R.x),R.u=0;}printf("0\n");exit(1);}

```

### UnGolfed:

```
#define R r[i]
#define Z return
#define _(B,D,E) for(int B=E;B<D;B++)
struct {
    int x,y,u,p;
} r[25],*S;
int A,M,N,U,V,X,Y;
char *P;

test_space(x,y,w,h) {
    _(I,x+w,x)
        _(J,y+h,y)
            if (    I >= U |
                    J >= V |
                    P[J*U+I]) Z 0;
    Z 1;
}
place_rect(x,y,w,h,c){
    _(I,x+w,x)
        _(J,y+h,y)P[J*U+I] = c;
}

fill_rest() {
    int x=0,y;
    while(++x<A) if (!P[x])break;
    if (x>=A) {
        _(i,V,0) printf("%*.*s\n", U,U, P+i*U);
        exit(0);
    }
    y = x / U; x -= y*U;

    _(i,N,0)
        if (!R.u & test_space(x, y, R.x, R.y))
                R.u = 1,
                place_rect(x, y, R.x, R.y, 'A'+i),
                fill_rest(),
                R.u = 0,
                place_rect(x, y, R.x, R.y, 0);

}

fill_y(i,y) {
    if (!R.u) {
        if (!test_space(0, y, R.x, R.y)) Z;
        R.u = 1;
        R.p = 0;
        place_rect(0, y, R.x, R.y, 'A'+i);
        y += R.y;
    }
    if (y == V) fill_rest();
    else _(j,N,0)
        if (j!=i && !r[j].u){ fill_y(j, y);
        while (r[j].x^r[j+1].x||r[j].y^r[j+1].y)j++;
        }
    R.u = 0;
    place_rect(R.p, (y -= R.y), R.x, R.y, 0);
}

fill_x(i,x) {
    if (!R.u) {
        if (R.x > U - x) Z;
        R.u = 1;
        R.p = x;
        place_rect(x, 0, R.x, R.y, 'A'+i);
        x += R.x;
    }
    if (x == U) fill_y(i, 1);
    else
        _(j,N,0)
            if (j!=i && !r[j].u) fill_x(j, x);
    place_rect((x -= R.x), 0, R.x, R.y, 0);
    R.u = 0;
}
C(int*a,int*b) {
    Z *a^*b?*a-*b:a[1]-b[1];
}

main() {
    _(i,25,0)
        if (++N&&scanf("%d %d\n", &R.x, &R.y)!=2) break;
    _(i,N,0){
        A+=R.x*R.y;
        if(R.x>X)X=R.x;
        if(R.y>Y)Y=R.y;
    }
    _(i,A+1,1)
        if (!(A%i)) {
            if (i < Y | A/i < X) continue;
            M++;
            S = realloc(S,M*16);
            S[M-1].y=i;
            S[M-1].x=A/i;
        }
    qsort(S, M, 16,C);
    P = calloc(A + 1,1);
    _(j,M,0){
        U = S[j].x; V = S[j].y;
        _(i,N,0)
            R.u = 1,
            place_rect(0, 0, R.x, R.y, 'A'+i),
            fill_x(i, R.x),
            R.u = 0;
    }
    printf("0\n");
    exit(1);
}

```

**Explanation:** We have 6 functions: `main`, `O`, `Q`, `F`, `L` and `T`. `T` **t**ests to see if there is space for the rectangle at a given spot. `L` fil**l**s a rectangle into the output buffer or, alternately removes one by overwriting it. `O` and `Q` build up the left and top walls, respectively and `F` **f**ills the remainder of the rectangle by iterative search.

Although the basic search is iterative, we eliminate the vast majority of possible search vectors, first by building up the allowed combinations of width and height for the master rectangle and then eliminating impossible configurations. Additional speed could be gained in larger rectangles by determining bottom and right walls prior to filling the center but it is not required for decent speed when limiting to 25 interior rectangles.
> 5 votes

# Answer
# Haskell, 226 bytes

```
((y,z):l)&(w,x)|x*y<1=(w+y,x+z):l
(q:l)&p=p:q:l
(p@(u,v):r@(y,z):l)%q@(w,x)=[((y-w,z):l)&q&(u,v-x)|w<=y,x<=v]++[p:m|m<-(r:l)%q]
_%_=[]
g m(p:n)l=any(g[]$m++n)(l%p)||g(p:m)n l
g[]_[_,_,_]=0<1
g _[]_=0<0
($[(0,9^9),(9^9,0)]).g[]

```

Try it on Ideone

### How it works

This recursively searches for all partial tilings whose shape is a Young diagram, adding one rectangle at a time, and checks whether any of the final results are rectangles.

To see that any tiling of a rectangle can be built this way: in any tiling of a nonempty Young diagram, let R be the set of rectangles in the tiling whose southwest corner does not touch any other rectangle. Since each concave vertex of the Young diagram is edge-adjacent (not merely corner-adjacent) to at most one rectangle in R, and the number of these concave vertices is one less than the number of rectangles in R, there must be at least one rectangle in R that is edge-adjacent to none of these concave vertices. Removing it yields another Young diagram, so we can proceed by induction.
> 6 votes

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


title: Github Messenger

text:
# Question
Title: Github Messenger
**Goal:** This goal to take a string and output how many contributions should be made on which days in order to display a message.

## Specification

* Input
    + Support letters plus space (i.e. `[A-Za-z ]` )
    + Space is a blank `3X7`
    + The letters are defined in this 5x7 DOT Matrix font provided below
    + The size of each letter is the minimum bounding rectangle (e.g. `l = 3x7`, `e = 5x5`)
* Coloring
    + There are 5 colors `C0, C1, C2, C3, C4`
    + `CX` requires `Y` contributions with `3X <= y < 3(X+1)`
    + Letters should alternate between `C1` and `C2`
    + Spaces have no color
    + Each letter size should overlap exactly 1 column with adjacent letters
    + If a cell has more than 1 color then use `C3`
* Dot Matrix
    + The dot matrix is Github's contribution history graph
    + If today is Monday, May 1st, 2017:

```
 4-30    5-07    5-15
[5-01]   5-08    5-16
 5-02    5-09     .
 5-03    5-10     .
 5-04    5-12     .
 5-05    5-13
 5-06    5-14

```
* Output
    + Flexible on how this is given
    + `(x, y)` pairs
    + `x` is a date greater than or equal to the current date
    + `y` is the number of contributions to be made on the date, `x`
    + Should be in chronological order (so I can fill in my calendar)
    + If for each date, `x`, the given `y` contributions are made, the input message should show up on the Github graph (with correct coloring)
    + The first date should the earliest possible
* Scoring
    + Shortest program/function in bytes wins

---

# Alphabet

Created by sylvan.black under CC

---

# Test Cases

For these test cases, assume the current date is May 25th, 2017.

```
Input -> Output
-----    ------
l        5-28-17, 3
         6-3-17, 3
         6-4-17, 3
         6-5-17, 3
         6-6-17, 3
         6-7-17, 3
         6-8-17, 3
         6-9-17, 3
         6-10-17, 3
         6-17-17, 3

He       5-28-17, 3
         5-29-17, 3
         5-30-17, 3
         5-31-17, 3
         6-1-17, 3
         6-2-17, 3
         6-3-17, 3
         6-7-17, 3
         6-14-17, 3
         6-21-17, 3
         6-25-17, 3
         6-26-17, 3
         6-27-17, 3
         6-28-17, 9
         6-29-17, 9
         6-30-17, 9
         7-1-17, 3
         7-4-17, 6
         7-6-17, 6
         7-8-17, 6
         7-11-17, 6
         7-13-17, 6
         7-15-17, 6
         7-18-17, 6
         7-20-17, 6
         7-22-17, 6
         7-26-17, 6
         7-27-17, 6

o W      5-31-17, 3
         6-1-17, 3
         6-2-17, 3
         6-6-17, 3
         6-10-17, 3
         6-13-17, 3
         6-17-17, 3
         6-20-17, 3
         6-24-17, 3
         6-28-17, 3
         6-29-17, 3
         6-30-17, 3
         7-9-17, 6
         7-10-17, 6
         7-11-17, 6
         7-12-17, 6
         7-13-17, 6
         7-14-17, 6
         7-22-17, 6
         7-26-17, 6
         7-27-17, 6
         7-28-17, 6
         8-5-17, 6
         8-6-17, 6
         8-7-17, 6
         8-8-17, 6
         8-9-17, 6
         8-10-17, 6
         8-11-17, 6

```

# Answer
> 11 votes
# JavaScript (ES6), 743 bytes

```
s=>(n=y=>d.setDate(d.getDate()+y),d=new Date,(h=d.getDay())&&n(7-h),r={},i=0,[...s].map(c=>{c<"!"?n(14):([...parseInt("jn4x733nx8gjw6nhricv6nx8dpz2vilui81vikl7b4nhridnzvgc1svznx8dji8g16fkg0vgc6341vg38oe9vh669ofvgm1dvjnhricvyvikl7aonhrjrjxvikmm29m0rqqp2nqmi6o0vbnf6dav2t14e4vbnjqpqs0g34o3tlqqwdso43oixtg1uyt8vvgddxn2hizrn2ahizrmdbhj4suq4gtytq8wgshvtzyvgc4mq7gzhwhz4g15ymf4vg72q9snx7r2f4jmffjm7jm5gavjhizrn2mjmkh3wogsgmianjm5gavcgwxpc3mhvni2kijhgqujjj8mcsgsjhgslnihw2cx75iqyv1cuhwdrh5d".substr((c.charCodeAt()-(c>"`"?71:65))*7,7),36).toString(2).slice(1).replace(/(0{7})+$/,"")].map(b=>(+b&&(r[+d]=r[+d]?9:i%2?6:3),n(1))),i++,n(-7))}),Object.keys(r).map(k=>[k,r[k]]).sort((i,j)=>i[0]-j[0]>0?1:-1).map(i=>[(new Date(+i[0])+"").slice(4,15),i[1]]))

```

Output is an array of 2-item arrays in the form `[dateString, contribs]`. The snippet below shows how that can be formatted into being more readable.

## Un-Golfed

```
s=>(
    n=y=>d.setDate(d.getDate()+y),
    d=new Date,
    (h=d.getDay()) && n(7-h),
    r={},
    i=0,
    [...s].map(c=>{
        c<"!" ? n(14) : (
            [...parseInt("<...>".substr((c.charCodeAt()-(c>"`"?71:65))*7,7),36).toString(2).slice(1).replace(/(0{7})+$/,"")].map(b=>(
                +b && (r[+d] = r[+d] ? 9 : i%2?6:3),
                n(1)
            )),
            i++,
            n(-7)
        )
    }),
    Object.keys(r)
        .map(k=>[k,r[k]])
        .sort((i,j)=>i[0]-j[0] > 0 ? 1 : -1)
        .map(i => [ (new Date(+i[0])+"").slice(4,15), i[1] ])
)

```

Where `<...>` represents the 364-byte string of characters that I created to encode each letter's dot matrix form.

## Explanation

The encoded string:

```
jn4x733nx8gjw6nhricv6nx8dpz2vilui81vikl7b4nhridnzvgc1svznx8dji8g16fkg0vgc6341vg38oe9vh669ofvgm1dvjnhricvyvikl7aonhrjrjxvikmm29m0rqqp2nqmi6o0vbnf6dav2t14e4vbnjqpqs0g34o3tlqqwdso43oixtg1uyt8vvgddxn2hizrn2ahizrmdbhj4suq4gtytq8wgshvtzyvgc4mq7gzhwhz4g15ymf4vg72q9snx7r2f4jmffjm7jm5gavjhizrn2mjmkh3wogsgmianjm5gavcgwxpc3mhvni2kijhgqujjj8mcsgsjhgslnihw2cx75iqyv1cuhwdrh5d

```

Each 7 characters is a base-36 encoded binary number that contains the mapping for the character at that index. The binary form always has a leading `1` in order to preserve the leading `0`s. For example, an uppercase `T` maps to `nqmi6o0`, which converts to `1100 00001000 00011111 11100000 01000000`. Skipping the leading 1, each bit is one day. Most numbers have 5 columns/weeks, so the numbers with less than 5 columns have one or two sets of 7 trailing zeros that are later removed before parsing (`.replace(/(0{7})+$/,"")`). This keeps all encoded strings the same length, removing the need for delimiters.

There's probably still more ways to improve upon this, especially with compressing the letter mappings further, so feel free to share any ideas.

Binary format of the letter mappings (JS syntax, prefixed with `0b`), can be found here.

## Basic Snippet

```
f=
s=>(n=y=>d.setDate(d.getDate()+y),d=new Date,(h=d.getDay())&&n(7-h),r={},i=0,[...s].map(c=>{c<"!"?n(14):([...parseInt("jn4x733nx8gjw6nhricv6nx8dpz2vilui81vikl7b4nhridnzvgc1svznx8dji8g16fkg0vgc6341vg38oe9vh669ofvgm1dvjnhricvyvikl7aonhrjrjxvikmm29m0rqqp2nqmi6o0vbnf6dav2t14e4vbnjqpqs0g34o3tlqqwdso43oixtg1uyt8vvgddxn2hizrn2ahizrmdbhj4suq4gtytq8wgshvtzyvgc4mq7gzhwhz4g15ymf4vg72q9snx7r2f4jmffjm7jm5gavjhizrn2mjmkh3wogsgmianjm5gavcgwxpc3mhvni2kijhgqujjj8mcsgsjhgslnihw2cx75iqyv1cuhwdrh5d".substr((c.charCodeAt()-(c>"`"?71:65))*7,7),36).toString(2).slice(1).replace(/(0{7})+$/,"")].map(b=>(+b&&(r[+d]=r[+d]?9:i%2?6:3),n(1))),i++,n(-7))}),Object.keys(r).map(k=>[k,r[k]]).sort((i,j)=>i[0]-j[0]>0?1:-1).map(i=>[(new Date(+i[0])+"").slice(4,15),i[1]]))

I.value="Hello World";
(I.oninput=_=>O.innerHTML = f(I.value).map(e=>e.join(": ")).join("\n"))();
```

```
<input id="I">
<pre id="O">
```

## Interactive example

Using the library cal-heatmap, I created an interactive heatmap of the dates that are output. This was used to test everything while working, and it just looks plain neat.

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


title: ROT13 and upside-down text (flip text)

text:
# Question
Title: ROT13 and upside-down text (flip text)
When I saw this title in the Hot Network Questions I thought it was going to be a PPCG challenge. I was a little disappointed when it was on Mathematica.

So now it is on PPCG:

## Challenge

Given an input string, output the ROT13, flipped value. The input will contain characters from the following alphabet: `[abcdefghijklmnopqrstuvwxyz <flipped alphabet>]`1

The flipped alphabet can be anything visually similar to the flipped lowercase Latin alphabet so long as it can be accepted as input.

The space character should remain unchanged.

As an example, your flipped alphabet might be `zʎxʍʌnʇsɹbdouɯlʞɾᴉɥƃɟǝpɔqɐ`

## Example

```
Input:    caesar woz ere
Rot13:    pnrfne jbm rer
Output:   ɹǝɹ ɯqɾ ǝuɟɹud

Input:    ɹǝɹ ɯqɾ ǝuɟɹud
Rot13:    pnrfne jbm rer
Output:   caesar woz ere

```

## Scoring

Simple , the lowest number of bytes wins.

---

I think this is different enough to the proposed duplicate for a few reasons:

* The answerer has the choice of which characters to use as output (within limits)
* The process should be reversible. i.e. flipped text should be acceptable as input and return "normal" text.
* There is the opportunity for graphical solutions in this question.

# Answer
# Python 3, 120 bytes

*many bytes saved thanks to @JonathanAllan*

```
lambda s,a='abcdefghijklmnopqrstuvwxyz VOďƄɹ5ʇη^MXʎ2ɐʠ>Pəɟ6ɥ!ɾʞ|W ':''.join(a[(a.find(c)+27)%54]for c in s)

```

Try it online!
> 1 votes

# Answer
# Mathematica, 234 bytes

```
T=ToExpression;B=Characters;L=T@CharacterRange["a","z"];K=T@B@"uodbɹsʇnʌʍxʎzɐqɔpǝɟƃɥᴉɾʞlɯ";(If[Max@ToCharacterCode@#<123,A=L;F=K,A=K;F=L];S=Association@Table[ToRules[A[[Z]]==F[[Z]]],{Z,Length@L}];Row@Reverse@T@B@#/.S)&

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Insert a simulated Ken Thompson virus into a program
A Ken Thompson virus is a virus that infects your compiler and other programs. Since it infects all your tools, you can not detect it without using tools from before the virus was introduced.

Your will create a prototype for inserting the Ken Thompson virus into code. The goal of this virus will be to allow you to (fake) destroy any computer running a program infected with it.

Inserting a Ken Thompson virus is defined as follows. Start with an input program `P`. Your program will output a modified program `Q` that works as follows:

* If the input to `Q` is `aNouIQ5xKvUfdZVzo0Xs`, it will output `BOOM` (in a real Ken Thompson virus, this would actually do something bad, but since it this is a fake virus, outputing `BOOM` is done instead).
* For any other input to `Q`, run program `P` with that input
    + If the output of `P` is valid source code in the language you are using, insert the Ken Thompson virus into it and then `Q` will output the resulting infected program.
    + Otherwise, the output of `Q` is just the output of `P`.

You will write a program that takes `P`'s code as input and produces `Q`'s code as output.

You can use either a currently (at the time of this post) existing programming language, or a subset of one, for this challenge. (The idea is that language you are using would be the target language of some self-compiling compiler, but this is not required.) Since you want to be as subtle as possible, the shortest code (in bytes) wins!

# Answer
> 2 votes
For some other languages, determining `If the output of P is valid source code in the language you are using` is almost impossible, unless you use/rewrite a compiler. For some other languages you can `eval` a string and catch for error, if any. However, for `Mathematica`, it is just check for if the head of the result is a function - Mathematica doesn't allow output invalid function, like `1!-!&`.

So,

## Mathematica, 209 bytes

(obviously can be golfed more, for example by assign long names to global variables)

```
With[{p=#,c=With[{p=#,c=6},If[#==="aNouIQ5xKvUfdZVzo0Xs","BOOM",With[{r=p@#},If[Head@r===Head@p,(c/.3!->c)[r],r]]]&]&},If[#==="aNouIQ5xKvUfdZVzo0Xs","BOOM",With[{r=p@#},If[Head@r===Head@p,(c/.3!->c)[r],r]]]&]&

```

The function takes a function as input, and output a function according to the specification.

Note that the input must be a pure function, not something like `f[x_] := ...`. So all Mathematica built-in functions fail the criteria.

Although *Mathematica* have `#0` parameter, I explicitly disallow that in my answer because a quine is not allowed to read the code of itself.

(I thought that question is trivial until I read the third rule)

---
Tags: code-golf, quine, code-generation
---


# Question
Title: Counting N-bit integer multiplication overflows
Given a positive integer `N`, output the number of pairs of integers `0 <= a <= b < 2**N` such that `a*b >= 2**N`.

## Rules

* You may assume that `N` is less than or equal to the maximum bit width for integers in your language (e.g. for C, `N` will not exceed `32` or `64`, depending on the architecture of the machine). If your language is capable of handling arbitrary-width integers, then there is no upper bound on `N`.

## Test Cases

```
1 0
2 3
3 19
4 96
5 437
6 1876
7 7804
8 31904
9 129170
10 520135
11 2088143
12 8369175
13 33512744
14 134128704
15 536681553
16 2147082274

```

# Answer
> 8 votes
# Python 2, ~~75~~ 68 bytes

```
n=input()
a=1<<n
s=~-a*a/2
x=y=0
while y<1:s+=y;x-=1;y=a/x-x
print s

```

Try it online!

This runs in O(2*n*/2) operations rather than O(2*n*) or O(2*n*), so it works on much larger inputs.

(Note that an even faster O(2*n*/3) algorithm exists.)

```
1 0
2 3
3 19
4 96
5 437
6 1876
7 7804
8 31904
9 129170
10 520135
11 2088143
12 8369175
13 33512744
14 134128704
15 536681553
16 2147082274
17 8589086503
18 34357951447
19 137435198086
20 549747939928
21 2199006781125
22 8796058620153
23 35184300378083
24 140737339120148
25 562949643323164
26 2251799170232606
27 9007197921321922
28 36028794259096612
29 144115182370060793
30 576460740519709546
31 2305842984902014765
32 9223371986742908935
33 36893488044218344323
34 147573952377320833218
35 590295809922086353118
36 2361183240537767708679
37 9444732963897547996897
38 37778931859178411534913
39 151115727444080615797321
40 604462909791437463796926
41 2417851639196741979223299
42 9671406556850476410936322
43 38685626227531971124247499
44 154742504910394112443480979
45 618970019642121099638818409
46 2475880078569598086230187969
47 9903520314280668496162705117
48 39614081257127323838921620439
49 158456325028518790167805606609
50 633825300114094540502620959956
51 2535301200456417702087608942034
52 10141204801825751449333352568660
53 40564819207303170200956592005599
54 162259276829213015854387448792578
55 649037107316852746005301421147606
56 2596148429267412374169967907532731
57 10384593717069652326923914077600197
58 41538374868278615068076777292632146
59 166153499473114471992855423428749242
60 664613997892457911812090466987383188
61 2658455991569831695728843704244440740
62 10633823966279326881474627069404687424
63 42535295865117307726213589942623257944

```

# Answer
> 5 votes
# Jelly, ~~12~~ 10 bytes

```
2*ṖµṀ:«ạ¹S

```

Finishes the combined test cases in under 3 seconds.

Try it online!

### How it works

```
2*ṖµṀ:«ạ¹S  Main link. Argument: n

2*          Yield 2ⁿ.
  Ṗ         Pop; yield A := [1, ..., 2ⁿ-1].
   µ        New monadic chain. Argument: A
    Ṁ       Maximum; yield 2ⁿ-1.
     :      Divide 2ⁿ-1 by each k in A.
      «     Dyadic minimum; yield min((2ⁿ-1)/k, k) for each k in A.
        ¹   Identity; yield A.
       ạ    Absolute difference; yield k - min((2ⁿ-1)/k, k) for each k in A.
         S  Take the sum.

```

# Answer
> 5 votes
# MATL, ~~10~~ 9 bytes

```
Wqt:&*R<z

```

Try it online!

This tries all possible pairs. It runs out of memory in the online interpreter for input exceeding `12`.

### Explanation

```
W      % Implicitly input N. Push 2^N ('^' denotes power)
q      % Subtract 1: gives 2^N-1
t:     % Duplicate, range: pushes [0 1 2 ... 2^N-1]
&*     % Matrix of all pair-wise products
R      % Upper triangular part (including diagonal)
<      % Less-than comparison; element-wise. This gives true for products
       % that are greater than 2^N-1
z      % Number of non-zeros- Implicitly display

```

# Answer
> 4 votes
# Brachylog, 21 bytes

```
;2↔^P>B≥Aℕ;B C×≥P∧C≜ᶜ

```

Try it online!

# Answer
> 3 votes
## JavaScript (ES7), ~~70~~ ~~65~~ 60 bytes

```
n=>[...Array(k=2**n-1)].reduce(p=>p+=k<++i*i&&i-(k/i|0),i=0)

```

### Test cases

```
let f =

n=>[...Array(k=2**n-1)].reduce(p=>p+=k<++i*i&&i-(k/i|0),i=0)

for(n = 1; n <= 16; n++) {
  console.log(n, f(n))
}
```

# Answer
> 3 votes
# 05AB1E, ~~13~~ 12 bytes

-1 byte thanks to Emigna

```
oDL<ã€{ÙP›_O

```

Try it online!

### Explanation

```
oDL<ã€{ÙP›_O   Argument n
oD             2^n, push twice to the stack
  L<           List: [0 .. a]
    ã          Cartesian product with itself
     €{        Sort each element
       Ù       Uniquify
        P      Total product of each element
         ›_    Each element is greater or equal than 2^n
           O   Total sum

```

# Answer
> 2 votes
## Mathematica, 37 bytes

```
Sum[#-⌈#/a⌉~Max~a,{a,#-1}]&[2^#]&

```

Try it online at http://sandbox.open.wolframcloud.com. Mathematica does not have limit on integers, and this algorithm run in time 2n, so it is very slow for large `n`.

# Answer
> 1 votes
## Clojure, 78 bytes

```
#(count(for[l[(bit-shift-left 1 %)]a(range l)b(range a l):when(>=(* a b)l)]1))

```

# Answer
> 1 votes
# Actually, 13 bytes

```
╙;r⌠;R*i⌡M♀≥Σ

```

Try it online!

A literal implementation of the problem. Quite slow.

# Answer
> 1 votes
# PHP, 62 bytes

```
for($x=$n=2**$argn;$y=--$x;)for(;$y;)$x*$y--<$n?:$r++;echo+$r;

```

Try it online!

# Answer
> 1 votes
# Python 2, 53 bytes

```
lambda n:sum(k-min(~-2**n/k,k)for k in range(1,2**n))

```

Try it online!

# Answer
> 0 votes
# Jelly, 11 bytes

```
2*’©ŒċP€>®S

```

Try it online!

A literal implementation of the problem. Quite slow.

---
Tags: code-golf, sequence, arithmetic, integer
---