# Question
Title: Sort a number's divisors by prime factorization
Given an input of an integer \\$n ≥ 2\\$, output a list of its divisors sorted by the exponents in their prime factorizations, in ascending order, ordering first by the largest prime, then by the second largest, and so on.

As an example, take the integer \\$72\\$, which is \\$2^3\cdot3^2\\$. It has the divisors

```
1     3^0 · 2^0
2     3^0 · 2^1
3     3^1 · 2^0
4     3^0 · 2^2
6     3^1 · 2^1
8     3^0 · 2^3
9     3^2 · 2^0
12    3^1 · 2^2
18    3^2 · 2^1
24    3^1 · 2^3
36    3^2 · 2^2
72    3^2 · 2^3

```

When sorted in ascending order by the exponents on the prime factors, with larger primes taking priority, this becomes

```
1     3^0 · 2^0
2     3^0 · 2^1
4     3^0 · 2^2
8     3^0 · 2^3
3     3^1 · 2^0
6     3^1 · 2^1
12    3^1 · 2^2
24    3^1 · 2^3
9     3^2 · 2^0
18    3^2 · 2^1
36    3^2 · 2^2
72    3^2 · 2^3

```

Note that the list is sorted first by the order of the exponent of 3, and then by the exponent of 2. You can also think of this as reading from left to right and top to bottom across the following grid:

```
        2^0  2^1  2^2  2^3

3^0     1    2    4    8
3^1     3    6    12   24
3^2     9    18   36   72

```

Test cases:

```
2 => 1 2
72 => 1 2 4 8 3 6 12 24 9 18 36 72
101 => 1 101
360 => 1 2 4 8 3 6 12 24 9 18 36 72 5 10 20 40 15 30 60 120 45 90 180 360
3780 => 1 2 4 3 6 12 9 18 36 27 54 108 5 10 20 15 30 60 45 90 180 135 270 540 7 14 28 21 42 84 63 126 252 189 378 756 35 70 140 105 210 420 315 630 1260 945 1890 3780
30030 => 1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210 11 22 33 66 55 110 165 330 77 154 231 462 385 770 1155 2310 13 26 39 78 65 130 195 390 91 182 273 546 455 910 1365 2730 143 286 429 858 715 1430 2145 4290 1001 2002 3003 6006 5005 10010 15015 30030
65536 => 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
74088 => 1 2 4 8 3 6 12 24 9 18 36 72 27 54 108 216 7 14 28 56 21 42 84 168 63 126 252 504 189 378 756 1512 49 98 196 392 147 294 588 1176 441 882 1764 3528 1323 2646 5292 10584 343 686 1372 2744 1029 2058 4116 8232 3087 6174 12348 24696 9261 18522 37044 74088

```

Since this is , the shortest code in bytes wins.

# Answer
# 05AB1E, 6 bytes

Code:

```
ÑÒí{€P

```

Explanation:

```
Ñ       # Get the divisors of input.
 Ò      # Factorize each.
  í     # Reverse each.
   {    # Sort the array.
    €P  # Product each.

```

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

# Answer
## Jelly, ~~8~~ 7 bytes

```
ÆDÆfU$Þ

```

Try it online! Thanks to @Dennis for -1 byte.

```
ÆD         Array of divisors, e.g. 24 -> [1, 2, 4, 8, 3, 6, 12, 24]
      Þ    Sort by...
     $       Combine previous two links...
  Æf           Factorise each, e.g. ['', [2], [3], [2, 2], [2, 3], [2, 2, 2],
                   [2, 2, 3], [2, 2, 2, 3]]
    U          Upend/reverse each sublist

```
> 8 votes

# Answer
# Jelly, ~~12~~ 10 bytes

**2 bytes thanks to @Sp3000.**

```
~~ÆE‘ḶUṚŒpUṚÆẸ~~
ÆEU‘ḶŒpUÆẸ

```

Try it online!

Test suite.

```
ÆE            Array of exponents, e.g. 24 -> [3, 1] since 24 = 2^3*3^1
  U           Upend/reverse, e.g. [1, 3]
   ‘Ḷ         Range of each, from 0, e.g. [[0, 1], [0, 1, 2, 3]]
     Œp       Cartesian product, e.g. [[0, 0], [0, 1], ..., [1, 3]]
       U      Upend, reversing the innermost lists
        ÆẸ    Inverse of ÆE, converting exponents back into a number

```

**Credits to @Sp3000 for coming up with the format of the explanation.**
> 7 votes

# Answer
# Pyth, 10 bytes

```
+1{*Mt_DyP

```

Try it online: Demonstration

Sadly the product over an empty list is not defined as 1 in Pyth. This costs three extra bytes.

### Explanation:

```
+1{*Mt_DyPQ   implicit Q (=input number) at the end
         PQ   prime factorization of input
        y     powerset
      _D      order by reversed subsets
     t        remove the empy subset
   *M         compute the product of each subsets
  {           remove duplicates
+1            prepend 1

```
> 7 votes

# Answer
## Python 2, 85 bytes

```
n=input()
p,=L=[1]
while~-n:
 l=L;p+=1
 while n%p<1:L=l+[x*p for x in L];n/=p
print L

```

No factorization, no sorting. Same-length recursive implementation:

```
f=lambda n,p=2:1/n*[1]or n%p and f(n,p+1)or[x*c for x in f(n/p)for c in[1,p][x%p<1:]]

```
> 7 votes

# Answer
## Actually, 19 bytes

```
;÷#o♂w♂RS`"iⁿ"£Mπ`M

```

Try it online!

Explanation:

```
;÷#o♂w♂RS`"iⁿ"£Mπ`M
;                    duplicate input
 ÷                   divisors
  #o                 include input in divisors list (note to self: fix this bug)
    ♂w               factor each integer into a list of [prime, exponent] pairs
      ♂R             reverse each list, so that the largest prime comes first
        S            sort the list
         `"iⁿ"£Mπ`M  for each factorization:
          "iⁿ"£M       for each [prime, exponent] pair:
           iⁿ            push prime**exponent
                π      product

```
> 5 votes

# Answer
## JavaScript, 78 bytes

```
f=(n,p=2,a=[1],b=a)=>n<2?a:n%p?f(n,p+1,a):f(n/p,p,a.concat(b=b.map(m=>m*p)),b)

```

Based on @xnor's idea, although I didn't understand his code so I had to reimplement it from scratch. The basic algorithm is that you start with \[1\] and multiply by \[1,...,pᵏ\] for each pᵏ in the prime factorisation of n, although as I don't have prime factorisation or cartesian product I have to do it all recursively. Example:

```
n=72 p=2 a=[1] b=[1]
n=36 p=2 a=[1,2] b=[2]
n=18 p=2 a=[1,2,4] b=[4]
 n=9 p=2 a=[1,2,4,8] b=[8]
 n=9 p=3 a=[1,2,4,8] b=[1,2,4,8]
 n=3 p=3 a=[1,2,4,8,3,6,12,24] b=[3,6,12,24]
 n=1 p=3 a=[1,2,4,8,3,6,12,24,9,18,36,72] b=[9,18,36,72]

```
> 5 votes

# Answer
## R, 196 bytes

```
n=scan()
if(n<4)c(1,n)else{
r=2:n
d=NULL
while(n>1){i=r[min(which(n%%r==0))];d=c(d,i);n=n/i}
m=unique(d)
b=table(d)
l=list()
for(i in 1:length(m))l[[i]]=m[i]^(0:b[i])
apply(expand.grid(l),1,prod)}

```

This is going to be inefficient as heck because I hardly resisted the temptation of using `library(primes)`. It creates a vector `d` of all prime factors of the input, computes their frequency (number of occurreces), and then computes the cartesian product of all possible powers (from 0 to the respective frequency `b[i]`), to which the `prod` function is applied. Dang it, special cases of 2 and 3! Otherwise, this is a nice showcase of R dataframe handling and vector functions / by-row operations (and even the purely statistical `table` function!).

Of course, its efficiency can be improved at the cost of 15 bytes using `r=2:ceiling(sqrt(n))`, if someone cares. Here is a nicer ungolfed version:

```
factorise <- function(n){
  if (n<4) c(1,n) else { # Now that all special cases have been handled
    r=2:ceiling(sqrt(n)) # We check all divisors smaller than the square root
    d=NULL # Initiate the variable for divisors
    while (n>1) {
      i=r[min(which(n%%r==0))] # Check the first divisor with a zero remainder
      d=c(d,i) # Append it to the list of divisors
      n=n/i   # Divide by it and check again
    }
    m=unique(d) # Get unique divisors, and they are already sorted
    b=table(d) # Count their frequencies
    l=list() # Initiate a list of all possible powers of unique factors
    for(i in 1:length(m)) l[[i]]=m[i]^(0:b[i]) # Calculate powers
    apply(expand.grid(l),1,prod) # Make a cartesian dataframe and row-multiply
  }
}

```
> 2 votes

# Answer
# Mathematica 150 bytes

```
f[t_]:=Thread@{#,IntegerExponent[t,#]&/@#}&@Prime@Range@PrimePi@Max@FactorInteger[t][[All,1]];Times@@@(#^#2&@@@#&/@Sort[Reverse/@(f@#&/@Divisors@#)])&

```
> 2 votes

# Answer
# Brachylog, 3 bytes

```
fḋᵒ

```

Try it online!

The code reads more or less just as the title of the challenge: "the factors of the input, sorted by their prime decompositions". Making sure that this 3-byte beauty actually passed the test cases using only Brachylog's built-in sense of how to sort lists ended up requiring me to copy and paste all those many numbers into the Clojure REPL, where list elements are separated by whitespace and commas are whitespace, but it turned out that it does indeed work.
> 2 votes

# Answer
# APL (Dyalog Extended), 17 bytes

Many thanks to ngn and Adám for their help in golfing both of these APL programs in The APL Orchard, a great place to learn APL and get APL help.

```
∊×⍀/⌽{⊂×\1,⍵}⌸⍨⍭⎕

```

Try it online!

**Ungolfing**

```
∊×⍀/⌽{⊂×\1,⍵}⌸⍨⍭⎕

                ⎕  Gets evaluated input from stdin.
               ⍭   Gives us a list of the prime factors of our input.
                   Example for 720: 2 2 2 2 3 3 5
     {      }⌸⍨    ⌸ groups our prime factors by the keys in the left argument,
                   and ⍨ passes the prime factors as both arguments,
                   grouping all the identical primes together
                   before running a {} dfn on them
      ⊂×\1,⍵       We append 1 to each group, get a list of powers of each prime,
                   and enclose the groups to remove 0s from uneven rows.
    ⌽             This reverses the prime power groups.
 ×⍀/              This multiplies all the powers together into
                   a matrix of the divisors of our input.
                   (Same as ∘.×/ in Dyalog Unicode)
∊                  And this turns the matrix into
                   a list of divisors sorted by prime factorization.
                   We print implicitly, and we're done.

```

---

# APL (Dyalog Unicode), 29 bytesSBCS

```
{∊∘.×/⌽{⊂×\1,⍵}⌸⍨¯2÷/∪∧\⍵∨⍳⍵}

```

Try it online!

**Ungolfing**

```
{∊∘.×/⌽{⊂×\1,⍵}⌸⍨¯2÷/∪∧\⍵∨⍳⍵}

{                           }  A dfn, a function in brackets.
                        ⍵∨⍳⍵   We take the GCD of our input with
                               all the numbers in range(1, input).
                     ∪∧\       This returns all the unique LCMs of
                               every prefix of our list of GCDs.
                               Example for 72: 1 2 6 12 24 72.
                 ¯2÷/          We divide pairwise (and in reverse)
                               by using a filter window of negative two (¯2).
                               Example for 72: 2 3 2 2 3, our prime factors.
       {      }⌸⍨              ⌸ groups our prime factors by the keys in the left argument,
                               and ⍨ passes the prime factors as both arguments,
                               grouping all the identical primes together
                               before running a {} dfn on them
           1,⍵                 We append 1 to each group.
        ⊂×\                    Then we get a list of powers of each prime,
                               and enclose the groups to remove 0s from uneven rows.
      ⌽                        This reverses the prime power groups.
  ∘.×/                         This multiplies all the powers together into
                               a matrix of the divisors of our input.
 ∊                             And this turns the matrix into a list of divisors
                               sorted by prime factorization.
                               We return implicitly, and we're done.

```
> 2 votes

# Answer
# J, ~~32~~ 31 bytes

```
[:(*/@#~>:#:[:i.[:*/>:)&|./2&p:

```

Grabs the lists of primes and exponents of the input integer, reverse each, and build up the divisors from that.

### Usage

```
   f =: [:(*/@#~>:#:[:i.[:*/>:)&|./2&p:
   f 2
1 2
   f 72
1 2 4 8 3 6 12 24 9 18 36 72
   f 101
1 101

```

### Explanation

```
[:(*/@#~>:#:[:i.[:*/>:)&|./2&p:  Input: n
                           2&p:  Factor n as a list where the first row are the primes
                                 and the second are their exponents
[:                     &|./      Reverse each list
                    >:           Increment each exponent by 1
                [:*/             Reduce it using multiplication
            [:i.                 Construct a range from 0 to that product exclusive
        >:                       The list of each exponent incremented
          #:                     Reduce each number in the previous range as a mixed base
                                 using the incremented exponents
      #~                         For each mixed base value in that range, copy from
                                 the list of primes that many times
   */@                           Reduce the copied primes using multiplication
                                 Return this list of products as the result

```
> 1 votes

# Answer
# Ruby, 71 bytes

This answer is based on xnor's Python 2 answer.

```
->n{a,=t=[1];(s=t;a+=1;(t=s+t.map{|z|z*a};n/=a)while n%a<1)while n>1;t}

```

A same-length alternative is:

```
->n{a,=t=[1];(a+=1;(t+=t.map{|z|z*a};n/=a)while n%a<1)while n>1;t.uniq}

```

**Ungolfing:**

```
def f(num)
  factor = 1
  list = [1]
  while num != 1
    s = list
    factor += 1
    while num % factor == 0
      list = s + list.map{|z| z*factor}
      num /= factor
    end
  end
  return list
end

def g(num)
  factor = 1
  list = [1]
  while num != 1
    factor += 1
    while num % factor == 0
      list += list.map{|z| z*factor}
      num /= factor
    end
  end
  return list.uniq
end

```
> 1 votes

# Answer
# Japt,  ~~12~~ 9 bytes

```
â mk ñÔ®×

```

*-3 bytes thanks to @Shaggy*

Try it online!
> 1 votes

# Answer
# Japt, 7 bytes

```
â ñ_k w

```

Run it online
> 1 votes

# Answer
# Mathematica, 56 bytes

```
1##&@@@Tuples@Reverse[#^Range[0,#2]&@@@FactorInteger@#]&

```
> 0 votes

---
Tags: code-golf, math, number, primes, sorting
---


title: Programming a Pristine World

text:
# Question
Title: Programming a Pristine World
Let's define a *pristine program* as a program that does not have any errors itself but will error if you modify it by removing any contiguous substring of \\$N\\$ characters, where \\$1 \le N \< \text{program length}\\$.

For example, the three character Python 2 program

```
`8`

```

is a pristine program <sup>(thanks, Sp)</sup> because all the programs resulting from removing substrings of length 1 cause errors (syntax errors in fact, but any type of error will do):

```
8`
``
`8

```

and also all the programs resulting from removing substrings of length 2 cause errors:

```
`
`

```

If, for example, ``8` had been a non-erroring program then ``8`` would not be pristine because **all** the results of substring removal must error.

Your task in this challenge is to write the shortest pristine program possible that takes no input but outputs any one of the following five words:

```
world
earth
globe
planet
sphere

```

Which word you choose is entirely up to you. The sole word plus an optional trailing newline should be printed to stdout (or your language's closest alternative). The shortest program in bytes wins.

**Notes:**

* A standalone program is required, not a function.
* The words are case sensitive; outputting `World` or `EARTH` is not allowed.
* Compiler warnings do not count as errors.
* The erroring subprograms can take input or give output or do anything else as long as they always eventually error.

Here's a stack snippet that will list what programs need to error given a potentially pristine program:

```
<script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>function go() { var s = $('#i').val(), e = []; for (var i = 1; i < s.length; i++) { for (var j = 0; j <= s.length - i; j++) { e.push(s.substring(0, j) + s.substring(j + i)); } } $('#o').val(e.join('\n---\n')); }</script>Program:<br><textarea id='i' rows='16' cols='80'>`8`</textarea><br><button onclick='go()' type='button'>Go</button><br><br>Programs that should error: (--- separated)<br><textarea id='o' rows='16' cols='80'></textarea><br>
```

# Answer
# Rail, 24 bytes

```
$'main'    #
 -[world]o/

```

I *think* this works. And it's both short and readable (as far as Rail goes).

* If the removed substring includes any part of `$'main'` we get `Internal Error: Crash: No 'main' function found`.
* If the removed substring includes the `#`, there is no way for the program to exit cleanly, so it will always terminate with `Crash: No valid move`. I believe that it's not possible to delete a substring such that the track forms a valid (infinite) loop.
* If the removed substring is in front of the `#`, it will be disconnected from the end of the track, so the train will crash (with the same error as above).
* If the removed substring is after the `#`, it will also disconnect the `#` from the end of the track (and potentially even the beginning of the track from the entry point `$`). So again the same error.

As for the actual program: every Rail program needs to have a `$'main'` (or a longer variant, but we're golfing here) as an entry point into the function and the train starts on the `$` going South-East. Everything on that first line can be part of the track though, so removing the `'main'` the track is:

```
$          #
 -[world]o/

```

The `-` and `/` are simply pieces of rail which we need to let the train take those 45° turns.

`[world]` pushes the string `world` and `o` prints it. `#` marks the end of the track - the only way to safely terminate a Rail program.

Interestingly, this solution is *only* possible because Rail allows the tracks to go through the `main` line - if that wasn't possible `#` would be after the first newline and the code could always be shortened to

```
$'main'
 #

```

which is a valid program that doesn't do anything. (Non-space characters between `'` and `#` wouldn't affect that.)

Also quite interesting: if I had just *golfed* the task printing `world` it wouldn't have been much shorter or simpler:

```
$'main'
 -[world]o#

```
> 51 votes

# Answer
# Funciton (~~186~~ 136 bytes in UTF-16)

```
╔══════════════╗
║19342823075080╟
║88037380718711║
╚══════════════╝

```

This program prints “world”.

Most substrings you remove from this will stop it from being a complete box, which the parser will complain about. The only possible removals that leave a complete box are:

```
 ╔══════════════╗
|║19342823075080╟  (remove this whole line)
|║88037380718711║
 ╚══════════════╝
 ╔══════════════╗
 ║|19342823075080╟   ← substring starts at | here
 ║|88037380718711║   ← substring ends at | here
 ╚══════════════╝
... ↕ or anything in between these that removes a whole line’s worth ↕ ...
 ╔══════════════╗
 ║19342823075080|╟   ← substring starts at | here
 ║88037380718711|║   ← substring ends at | here
 ╚══════════════╝
 ╔══════════════╗
|║19342823075080╟
 ║88037380718711║  (both lines entirely)
|╚══════════════╝
 ╔══════════════╗
 ║19342823075080╟
|║88037380718711║  (remove this whole line)
|╚══════════════╝

```

Most of these remove the dangling end at the top right of the box, which is the output connector. Without this loose end, the box is just a comment:

```
╔══════════════╗
║88037380718711║
╚══════════════╝

```

This is no longer a valid program because the parser expects a program with exactly one output:

> Error: Source files do not contain a program (program must have an output).

The only possibility that leaves an output connector is the last one of the above, which leaves this:

```
╔══════════════╗
║19342823075080╟
╚══════════════╝

```

However, this number does not encode a valid Unicode string in Funciton’s esoteric UTF-21. Try to run this, you get:

> Unhandled Exception: System.ArgumentOutOfRangeException: A valid UTF32 value is between 0x000000 and 0x10ffff, inclusive, and should not include surrogate codepoint values (0x00d800 ~ 0x00dfff).

Therefore, this program is pristine.
> 46 votes

# Answer
## Visual C++ - 96 95 bytes

```
#include<iostream>
#define I(a,b)a<<b
int main()I({std::cout,I('w',I('o',I('r',I('l','d';)))))}

```

**Properties:**

1. You can't remove any part of `int main()` without a compile error.
2. You can't remove the modify the macros expansion AT ALL, removing `a` at all means `main()` never gets `{`, removing `b` at all means our line doesn't end in a `;`, removing `<` means `std::cout<'w'` causes an error, and removing `<<` causes `std::cout'w'`, `'w''o'`, etc.
3. You can't remove parameters from the macro definition or invocation, the only valid names for the definition would be `I(a)`,`I(b)` which never match and `I` which expands to before `(`; on the other hand using `I(,` causes `<<<<`, and `,)` drops the semi-colon (barring any other errors).
4. You can't remove part of all of `std::cout` without running into a leading `<<`, and therefore cannot remove any of `#include<iostream>` in the beginning without a compile error.
5. You can't remove any part of a single character, `''` has an empty character error and `'w,`, etc... try to making everything into one character.
6. You can't remove the left/right side of a macro without leaving too many `)` or `(` on the other side, e.g. you cannot do things like `I('w',I('r'`.

Compiles online using Visual C++.

Once again this not an exhaustive proof. If you think you can get it too work without section be sure to let me know.

*Previous versions used a considerably different approach and was proved to not be pristine so I've removed those scores.*

---

**Verification:**

The following program has confirmed this version is pristine using the `cl` compiler from Visual C++ 2010. Wished I had bothered to write this sooner:

```
#include <fstream>
#include <iostream>
char *S = "#include<iostream>\n#define I(a,b)a<<b\nint main()I({std::cout,I('w',I('o',I('r',I('l','d';)))))}";
//uncomment to print source code before compile
// #define prints
int main(){
   for(int i=0; i<95; i++)
      for(int j=i; j<95; j++){
         std::fstream fs;
         fs.open ("tmptst.cpp",std::fstream::out);
         for(int k=0; k<95; k++)
         if(k<i || k>j){
            fs << S[k];
            #ifdef prints
               std::cout<<S[k];
            #endif
         }
         fs.close();
         #ifdef prints
            std::cout<<'\n';
         #endif
         //Compile and surpress/pipe all output
         //if it doesn't compile we get a nonzero errorlevel (i.e.true) from system.
         if(!system("cl -nologo tmptst.cpp >x"))
            return 0;
      }
      std::cout<<"PRISTINE!";
}

```
> 35 votes

# Answer
# Python 3, ~~79~~ 33

```
if 5-open(1,'w').write('world'):a

```

`open(1,'w')` opens standard output, then we print the string. `write` returns the number of characters written. This is used to harden against substring removal: Removing part of the string causes something other than 5 to be returned, and 5 minus that value then evaluates to true. But that causes the `if`-body to be executed and `a` is undefined.

This is based on Anders Kaseorg's clever pristine quine here.

As only a single statement needs to be verified this is much shorter than the old solution, but also less general.

### Old solution:

```
try:
 q="print('world');r=None"
 if exec('e=q')==eval(q[17:]):exec(e)
finally:r

```

To verify that it really is a pristine program:

```
w=r'''try:
 q="print('world');r=None"
 if exec('e=q')==eval(q[17:]):exec(e)
finally:r'''
exec(w)
for j in range(1,len(w)):
 for i in range(len(w)+1-j):
  e=w[:i]+w[i+j:]
  try:exec(e,{});print('WORKED',e)
  except:pass

```

Some key points:

* Every executed statement could be deleted. Verifying that `q` has been executed requires a statement outside of `q`. The `try` solves that nicely, by requiring at least two statements, neither of which can be deleted fully.
* Verifying that `q` has executed happens by evaluating `r` at the end.
* Verifying that `q` was not modified is achieved by `eval(q[17:])`, which has to evaluate to `None` for `q` to be executed.
* The `if` condition is a bit tricky to get right. To ensure that it was evaluated it has the nice side effect of setting `e`, which is needed to set `r`. (This is the reason I used Python 3, `expr` as a function does wonders for expression-level side effects.)
> 33 votes

# Answer
# Haskell, 61

```
x=uncurry(:)
main=putStr$x('w',x('o',x('r',x('l',x('d',[])))))

```

Any type of error is OK? In that case:

# Haskell, 39

```
main=putStr$take 5$(++)"world"undefined

```
> 27 votes

# Answer
# JavaScript, ~~74~~ ~~73~~ 35 bytes

```
if((alert(a="world")?x:a)[4]!="d")x

```

It turns out the answer was much simpler than I thought...

## Explanation

```
if(
  (
    alert(a="world") // throws a is not defined if '="world"' is removed
        ?x           // throws x is not defined if 'alert' or '(a="world")' is removed
        :a           // throws a is not defined if 'a="world"' or 'a=' is removed
  )
  [4]!="d"           // if "world" is altered fifth character will not be "d"
                     // if 'd' is removed it will compare "world"[4] ("d") with ""
                     // if '[4]' is removed it will compare "world" with "d"
                     // if '(alert(a="world")?x:a)' is removed it will compare [4] with "d"
                     // if '?x:a' is removed [4] on alert result (undefined[4]) will error
                     // if '[4]!="d"' is removed the if will evaluate "world" (true)
                     // if '!', '!="d"' or '(alert...[4]!=' is removed the if will
                     //     evaluate "d" (true)
)x                   // throws x is not defined if reached

// any other combination of removing substrings results in a syntax error

```
> 19 votes

# Answer
# Funciton, ~~143~~ ~~142~~ 136 bytes

Score is in UTF-8 as usual, as UTF-16 would be two bytes larger (due to the BOM).

```
╔══════════╗
║1934282307║╔╗
║5080880373╟╚╝
║80718711  ║
╚══════════╝

```

So, I've been contemplating a Funciton answer for a while and I figured it would be impossible, because you could always remove a full line and the code would still form a valid block. Then I talked to Timwi about it, and he figured out that you can just put the entire number in a single line, such that removing it would break the program for lack of an output connector.

But literals on a single line are notoriously expensive, both because of the larger character count *and* because of the larger number of non-ASCII characters. And his mention of an "empty comment" block got me thinking...

So I came up with this more efficient solution which uses an additional empty comment block which breaks when you try removing anything which would leave the literal block in tact:

* We can't possibly remove the third line, because then we'd remove the output connector.
* If we remove the second line, the comment block loses its top edge and breaks.

That leaves two options (thanks to Steve for pointing that out):

* Remove the fourth line. That leaves both boxes in tact. However, when the resulting integer `19342823075080880373` is decoded, the corresponding string would contain the code point `0x18D53B` which is not a valid Unicode character, `System.Char.ConvertFromUtf32` crashes with an `ArgumentOutOfRangeException`.
* Remove a full line starting after the top-right corner. Again, both boxes are left in tact, but the resulting integer `508088037380718711` would contain two invalid code points `0x1B0635` and `0x140077`, leading to the same exception.

Note that even without the empty comment block, removing the second line would lead to an invalid code point. But the comment block prevents that we're taking a line from *inside* the second line, to get an integer like `193428037380718711` for instance, which would not cause an error.
> 16 votes

# Answer
# Java 8, 301 bytes

Because every question needs a Java answer.

```
class C{static{System.out.print(((((w='w')))));System.out.print((((o='o'))));System.out.print(((r='r')));System.out.print((l='l'));System.out.print(d='d');e=(char)((f=1)/((g=8)-C.class.getDeclaredFields()[h=0].getModifiers()));}public static void main(String[]a){}static final char w,o,r,l,d,e,f,g,h;}

```

## Expanded

```
class C {
    static {
        System.out.print(((((w = 'w')))));
        System.out.print((((o = 'o'))));
        System.out.print(((r = 'r')));
        System.out.print((l = 'l'));
        System.out.print(d = 'd');
        e = (char) ((f = 1) / ((g = 8) - C.class.getDeclaredFields()[h = 0].getModifiers()));
    }

    public static void main(String[] a) { }

    static final char w, o, r, l, d, e, f, g, h;
}

```

## Explanation

* `public static main(String[]a){}` is required.
* If the field declarations are removed (or made non-static), the first static block can't find them.
* If the static block is removed (or made non-static), the fields aren't initialized.

### The hardest part:

* If the `final` keyword is removed, the second line evaluates to `1/(8-8)`, causing a `/ by zero` exception.
> 15 votes

# Answer
# \>\<\>, 17 bytes

```
e"ooooo7-c0pBhtra

```

Try it online!

Prints "earth".

The only way a `><>` program exits without an error is executing the `;` character, which is a problem as you can just remove all the characters before that, so that `;` is the first character executed. You can get around that by using the `p` command to modify the program to include `;` during execution instead. Removing any section of the code causes the `;` to never be produced causing errors via the invalid instructions `B`, `h` and `t`, stack underflow, and infinite loops making it eventually run out of memory. I only had to make sure that all the infinite loops kept filling up the stack.

All variants were tested using this python snippet:

```
code = 'e"ooooo7-c0pBhtra'
count = {"invalid":0, "underflow":0, "memory":0}
for l in range(1, len(code)):
    for x in range(0, len(code)-l+1):
        print(code[:x] + code[x+l:], "\t\t", end='')
        try:
            interp = Interpreter(code[:x]+code[x+l:])
            for _ in range(0,1000):
                interp.move()
            print(len(interp._stack), "< ", end='')
            interp2 = Interpreter(code[:x]+code[x+l:])
            for _ in range(0,2000):
                interp2.move()
            print(len(interp2._stack))
            count["memory"] += 1
        except Exception as e:
            print(e)
            if str(e) == "pop from empty list": count["underflow"] += 1
            else: count["invalid"] += 1
print(count)
#don't judge me

```

added to (a slightly modified version of) the official fish.py interpreter by the creator of \>\<\>. Out of 152 possible sub-programs, 92 errored from invalid instructions, 18 from stack underflow, and 42 from running out of memory.

Funny facts, the first version of this `e"ooooo6-c0pAhtra` had a couple of freak sub-programs that managed to use the put command to place a `[` which would clear the stack, in place of the invalid instruction `A`. Also, "earth" is the only one of the phrases that will work with this method, because the first letter, `e` is a valid instruction in `><>`. Otherwise the `"` command has to be placed at the front of the program, and a valid subprogram could be just `"` by itself.
> 15 votes

# Answer
# Ruby, 36

```
eval(*[(s="planet")[$>.write(s)^6]])

```

We assign `s="planet"`, then write that string to STDOUT. This returns the number of characters written. We xor that with 6, so that if anything other than 6 characters were written, we'll get a nonzero integer. Then we slice into `s` with that index. Only the 0th character of `s`, "p", is a valid code string (a no-op). We pass that to `eval`, using the `(*[argument])` syntax which is equivalent to just `(argument)` except that it's not valid outside of a method call.

Pristineness verified programmatically on Ruby 1.9.3 and 2.2
> 11 votes

# Answer
# C#, ~~128~~ ~~118~~ 101 bytes

Thought of abusing the contiguous substring rule.

**The Code**

```
class h{static void Main()=>System.Console.Write(new char[1
#if!i
*5]{'w','o','r','l','d'
#endif
});}

```

**Why It Works**

1. `class h` and `static void Main()` are required.
2. Removing any of the chars in `'w','o','r','l','d'` causes an error because the char array is initialized with length `1*5`.
3. You can't remove the contents inside Main() without violating the contiguous character rule as parts are separated by preprocs. (See below)

**Before Golfing and Separation**

```
class h
{
    static void Main() =>
        System.Console.Write(new char[1 * 5]{'w','o','r','l','d'});
}

```

**Verified With**

https://ideone.com/wEdB54

EDIT:

* Saved some bytes by using `#if !x` instead of `#if x #else`.
* Used `=>` func syntax. `#if!x` instead of `#if !x`. Credits to @JohnBot.
* Due to `=>` func syntax, extra preproc condition can be removed.
> 10 votes

# Answer
## MATLAB, 37 36 33 bytes

```
feval(@disp,reshape('world',1,5))

```

Since I am not sure if we are allowed to also output *ans=*, I had to find some work-around to output in a proper way. Using *fprintf* by itself did not work, because no matter what I tried it simply refused to error. Using *disp* by itself was not an option, as it would only take 1 argument and that argument itself obviously would also execute without errors.

If it's no problem to also include *ans=* in the output, then MATLAB can be done with **20 bytes**:

```
reshape('world',1,5)

```
> 10 votes

# Answer
# Ruby, 34

```
eval(*[($>.write("world")-1).chr])

```

This has a few components:

`eval(*[` *expr* `])` is borrowed from histocrat's answer, and is pristine as well as verifying the return value of *expr* is a valid ruby program that doesn't error. `method(*arr)` is a ruby syntax that calls `method` with the values of `arr` as the arguments. The reason this is needed here is because it is *only* valid as parameters for a method, so that if `eval` is removed, `(*[expr])` is a syntax error. If *expr* is removed, `eval` complains about not having enough arguments

`$>.write("world")-1` cannot be mangled except for inside the string and the subtraction. `$>.write("world")` writes "world" to STDOUT and returns the number of characters written, then subtracts 1. Therefor if the program is un-mangled the value will be exactly **4**. If it is mangled (either the `-1` is removed or the string shortened) then it will return one of **-1,0,1,2,3, or 5**. Any other mangling results in a syntax error.

Calling `chr` on a number returns the character represented by that number. So, when called on the result of the above example, it errors on -1, and returns a single-character string otherwise.

I'm not actually sure why this is, but it seems that ruby interprets `\x04` as a whitespace character, which means the expression is valid (empty ruby programs do nothing). However, any of the other characters (`\x00` \- `\x03` and `\x05`) result in `Invalid char '\x01' in expression`. I found this by simply iterating over possible math I could do to the number returned. Previously I had used

```
$>.write("planet
")*16

```

where "planet" plus a newline was 7 chars, times 16 to get 112 for `p`, the only single-letter function in ruby defined by default. When given no arguments, it is effectively a no-op

---

Honorable mention: `$><<"%c"*5%%w(w o r l d)` is very close but not pristine. Removing `"%c"*5%` results in no errors. Mini-explanation:

`$>` is stdout, and `<<` is a function being called on it. `"%c"*5` generates the format string `"%c%c%c%c%c"`, which then then trys to be formatted (`%`) by an array: `%w(w o r l d)` which is a shorter version of `['w','o','r','l','d']`. If there are too few or too many elements in the array such that it does not match the format string, an error is thown. The achilles heel is that `"%c"*5`, and `%w(w o r l d)` can both exist independantly, and `$><<` only needs an argument of either. So there are a few different ways of mangling this program into non-erroring cousins.

---

Validated using this:

```
s = 'eval(*[($>.write("world")-1).chr])'
puts s.size
(1...s.length).each do |len| #how much to remove
  (0...len).each do |i| #where to remove from
    to_test = s.dup
    to_test.slice!(i,len)
    begin #Feels so backwards; I want it to error and I'm sad when it works.
      eval(to_test)
      puts to_test
      puts "WORKED :("
      exit
    rescue SyntaxError
      #Have to have a separate rescue since syntax errors
      #are not in the same category as most other errors
      #in ruby, and so are not caught by default with
      #a plain rescue
    rescue
      #this is good
    end
  end
end

```
> 8 votes

# Answer
# Python 3, 43 bytes

```
for[]in{5:[]}[open(1,"w").write("world")]:a

```

Try it online!

### How it works

To protect against substring deletions, we use `open(1,"w").write` instead of `print`. In Python 3, `write` returns the number of written characters, which we will verify is `5` to ensure that no part of the string was deleted. We do this by looking up the return value in the dictionary `{5:[]}`, and looping over the result with `for[]in…:a`, which will fail if we didn’t get an empty iterable or if the `for` statement is deleted.
> 6 votes

# Answer
# Ruby + coreutils, ~~33~~ ~~27~~ 26 bytes

```
`base#{$>.write"world
"}4`

```

Try it online!

Backticks in ruby execute the command inside them and return whatever the program put into STDOUT as a string. The `#{expr}` syntax allows embedding of expressions in strings and backticks. This program could be rewritten (non-pristinely) as:

```
system("base" + (STDOUT.write("world\n")).to_s + "4")

```

`IO#write` returns the number of bytes written, so if the string is shortened then it won't be the right number. `#{}` embedding automatically makes the number into a string. If some piece is removed, and it doesn't result in a syntax error, the wrong command will be run. If part of `"world"` is removed than one of `base04` through `base54` will try to run.

The newline, whether in or out of the string, is required. Otherwise the first 5 characters(``base`) can be removed, making the whole line a comment. Also there must be one or more characters between the first backtick and `#`, otherwise the `{` can get removed to make the whole thing a *shell* comment.

---

```
exec(*[(s="ec%co earth")%s[10]])

```

`exec` Replaces the current ruby process with the command specified. See my other answer for an explanation of the `meth(*[])` syntax and the neccesity of it.

`(s="ec%co earth")` assigns the string "ec%co earth" to the variable `s`. Assignments return what was assigned, so the string is also returned.

`"format string %d" % 5` is syntactic sugar for `sprintf("format string %d",5)`, however spaces around the `%` are not neccesary.

`s[10]` gets the character in the string at index 10. When un-mangled, this character is "h", the last letter in the string. However, removing any characters in the string means the string is shorter, so there is no character at index 10, so `s[10]` returns `nil`, and `"%c" % nil` causes an error.

if `%s[10]` is removed, then ruby tries to run the command `ec%co earth` which doesn't work.

Changing `10` to `1` or `0` also results in an unknown command (either `eceo` or `ecco`). Removing it entirely is technically not a syntax error since it calls the method `#[]` on the string, but then it complains about not enough arguments.

---

A note on solving this in general: You must have some wrapper that verifies the code inside in an abstract sense while being pristine itself. For example, a program with division at the end (`blablabla/somevar`) will never work because a division can always be removed(`blablabla`). These are some such wrappers I've used so far:

* `eval(*[` code `])` used by histocrat and in my first answer. Validates that the output is a valid ruby program
* `exec(*[` code `])` used above, validates that the response is a valid command
* ``#{` code `}``

The backtick syntax also runs a command (and therefor validates that it's a valid one), however STDOUT is captured as a string instead of being output as the parent process' (Ruby's) STDOUT. ~~Due to this I was not able to use it for this answer,~~ EDIT: I made it work. Limitations outlined above.

Edit: Thanks to @histocrat for pointing out some flaws
> 5 votes

# Answer
# Perl 5.10+, ~~71~~ 63 bytes

```
(${open 0;@{\(read(0,$a,63)!=63?die:@_)};say"world"});{$a//die}

```

Prints `world` with a trailing newline. Run like this:

```
perl -M5.010 file

```

This relies on the byte count of the source code, so `file` must contain the above code and nothing else (no shebang, no trailing newline). Perl 5.10+ is required for `say` and the defined-or operator `//`.

---

It's incredibly difficult to make a pristine program with Perl, because:

* Any bareword identifier (e.g. `foo`, `a`, `_`) is a valid statement with `no strict 'subs';` (the default). This means the program can neither begin nor end with a letter, number, or underscore.
* As tchrist explains, "Identifiers specified via symbolic dereferencing have **absolutely no restriction whatsoever** on their names." This means the program cannot begin with any of the sigils `$`, `@`, `%`, or `*`, since removing all but the first and last character would always leave a valid variable name.
* Many built-in functions (including most functions capable of producing output) work on `$_` by default, so calls will often work even if you remove the argument (e.g. `say"world"` vs. `say`).

## How it works

This solution was inspired by Naouak's Node.js answer, which checks its own length to make sure characters haven't been removed.

The program has two sections, one inside parentheses and the other inside a block:

```
(...);{...}

```

The first section reads the source file and dies if it is less than 63 characters long. The second section checks that the `read` executed successfully. If either section is removed (with or without the enclosing parentheses or curly braces), the other section will throw an exception.

Removing the middle or the left or right side of the program will unbalance the parentheses and/or curly braces, causing a syntax error.

If the first `die` is altered (to `d`, `e`, `di`, `de`, or `ie`, which are all valid identifiers), the length check becomes:

```
@{\(read(0,$a,63)!=63?di:@_)};

```

which evaluates to:

```
@{\'di'};

```

This takes a reference to a string and tries to dereference it as an array, producing an error:

```
Not an ARRAY reference

```

If any other statement is altered, the length check will fail and the program will die.

---

Verified pristine with the following program:

```
#!/usr/bin/perl

use strict;
use warnings;
use 5.010;

use File::Temp;
use List::MoreUtils qw(uniq);

sub delete_substr {
    my ($str, $offset, $len) = @_;

    my $tmp = $str;
    substr($tmp, $offset, $len) = '';

    return $tmp;
}

sub generate_subprograms {
    my ($source) = @_;

    my $tot_len = length $source;
    my @subprograms;

    foreach my $len (1 .. $tot_len - 1) {
        foreach my $offset (0 .. $tot_len - $len) {
            push @subprograms, delete_substr($source, $offset, $len);
        }
    }

    return uniq @subprograms;
}

chomp(my $source = <DATA>);
my $temp = File::Temp->new;

foreach my $subprogram ( generate_subprograms($source) ) {
    print $temp $subprogram;

    my $ret = system(qq{/usr/bin/perl -M5.010 $temp > /dev/null 2>&1});
    say($subprogram), last if $ret == 0;

    truncate $temp, 0;
    seek $temp, 0, 0;
}

__DATA__
(${open 0;@{\(read(0,$a,63)!=63?die:@_)};say"world"});{$a//die}

```
> 5 votes

# Answer
# Javascript(Node.js), ~~93~~ 95 bytes

```
if(l=arguments.callee.toString().length,l!=158)throw l;console.log("world");if(g=l!=158)throw g

```

Check it's own size twice so if any chars is missing an error is thrown. The length is 156 because Node.js prepends `function (exports, require, module, __filename, __dirname) {` to the code on runtime.

Thanks Martin Büttner for pointing out an error. Fixed now.
> 4 votes

# Answer
# C (gcc) (Linux,`-Werror=undef`), 66 bytes

```
main(a){a
=
1
/
(puts("world")/
6);
#if(7^__LINE__)
#else
}
#endif

```

Try it online!

Great challenge! This was deceptively hard, but I'm pretty sure I have a valid program now!

Uses a preprocessor command so that no newlines can be removed, since the closing bracket to `main` is included only if `__LINE__==6`. It also keeps you from just clearing out `main` entirely, since that leaves `#endif` floating (so it is important that `#endif` is outside of `main`).

I used `#else` because I've become fairly convinced there's no version of `__LINE__==6` that can't have a substring removed and still be true, since both `6` and `__LINE__` by themselves are truthy. It also uses `-Werror=undef` so that something like `#ifdef(LINE__)` doesn't evaluate to false, but is an error.

With gcc (on Linux, at least), `puts` returns the number of characters printed (including the trailing newline), so removing any part of the string makes `puts("...")/6` return `0`, so that `1/0` causes a floating point exception. Note that this exception isn't caused unless `1/0` is assigned to something, so the `a=` is required.

No other part of any line can be removed without creating an error, usually a syntax error or a linking error.

As a bonus, this gives an 86 byte solution for C++ pretty trivially, just add `#include <cstdio>` and declare `a` as an `int`. Try it online! (C++)
> 4 votes

# Answer
## PowerShell, (97 bytes + 5 for program name) = 102 Bytes

```
"$(try{if(($a=(gc .\c.ps1).Length)-eq97){"world";a}}catch{if($a-ne97){a}$error.clear();exit}a)";a

```

Checks itself before it wrecks itself ... twice.

Expects to be saved as `c.ps1` and executed from the local directory as such:
`PS C:\Tools\Scripts\Golfing\> .\c.ps1`.

The alias `gc` is short for `Get-Content` and is similar-ish to a `cat` reading a file (in this case, our execution path `.\c.ps1`). We get the `.Length` of the file, set it to `$a`, and check whether it's not equal to 97 with `-eq97`. If it is equal (i.e., the program has not been modified), we print with `"world"`, and execute invalid command `a`. This forces the `catch` to take effect, which allows us to check ourselves again. This time, if our code is not equal to 97, we throw an invalid command so our program has errored and printed error text to the output. We then `clear()` the error and `exit` normally.

It's obvious that if either `if` statement is tampered with, the other will have an error. If any portion of `"world";` is tampered with, the first `if` will cause an error. Since it has to be contiguous, we can't remove both `if` statements. Strings in the middle will result in mismatched parentheses, or will result in the second `{a}` getting executed. The `try`/`catch` is to catch the error from the first `if` statement so we can properly clear it. The outer `"$( )"` prevent strings from either end getting snipped. The final `;a` is to prevent portions of the middle getting snipped that would result in valid programs (e.g., `"it}a)";a`, which will print `it}a)` and then error).

There are several special circumstances:

* If the `gc`, `gc<space>` or `gc .\` are removed, the program will eventually error out with some flavor of an out of memory error (due to repeated self-execution calls) and likely crash the shell (and maybe the computer). Not tested.
* If the `<space>.\c.ps1` or `.\c.ps1` are removed, the program will stop and prompt for user input. No matter what the user enters, the program will still error since the size counts will be wrong.
* If a substring starting at the `$` and ending before the last `"` is snipped, the program will output whatever remains and then error because `a` is not valid.

Verified with the following:

```
$x='"$(try{if(($a=(gc .\c.ps1).Length)-eq97){"world";a}}catch{if($a-ne97){a}$error.clear();exit}a)";a'
$yy='"$(try{if(($a=( .\c.ps1).Length)-eq97){"world";a}}catch{if($a-ne97){a}$error.clear();exit}a)";a'
$yyy='"$(try{if(($a=(.\c.ps1).Length)-eq97){"world";a}}catch{if($a-ne97){a}$error.clear();exit}a)";a'
$yyyy='"$(try{if(($a=(c.ps1).Length)-eq97){"world";a}}catch{if($a-ne97){a}$error.clear();exit}a)";a'

for($i=1;$i-lt$x.Length;$i++){
  for($j=0;$j-lt($x.Length-$i);$j++){
    $y=($x[0..$j]+$x[($i+$j+1)..$x.Length])-join''
    $y>.\c.ps1
    $error.clear()
    if(!($y-in($yy,$yyy,$yyyy))){try{.\c.ps1}catch{};if(!($error)){exit}}
    $q++;
    write-host -n "."
    if(!($q%150)){""}
  }
}
"No success."

```

(Thanks to Martin for his extensive assistance!)
> 3 votes

# Answer
# PHP, 73 bytes

```
<?=call_user_func(($p='ns')|(($f="u{$p}erialize"))?$f:'','s:5:"world"');

```

### Explination

I assume the default php.ini configuration. So short\_tags is disabled. This means you can't remove the `=` from the opening tag.

This is basically `<?=unserialize('s:5:"world"');`.

If you remove any part of the serialized string you'll get an error.

You can simply remove `unserialize` and the script will just output the serialized string. To overcome this I use `call_user_func`. Removing one of the params will result in an error.

```
'<?=call_user_func('unserialize','s:5:"world"');

```

However you can remove `un`, to call the `serialize` function. So we take out 'ns\`. Removing any characters would no result in an incorrect function name.

```
<?=call_user_func(($p='ns')&&($f="u{$p}erialize")?$f:'','s:5:"world"');

```

We'll use an inline if to using variable assignment with the output tag. Instead of using `&&` we use '|' to prevent removing a single `&` or removing the `$f` assignment

You could remove `='ns')&&($f="u{$p}erialize"` and end up with `($p)?$f:''`. Therefor I add extra parenthesis around `$f="u{$p}erialize"`.

### Note

*Technically you can remove the opening tags without producing an error. This is than however no longer a PHP script but just a plain text file.*
> 2 votes

# Answer
# A Pear Tree, 17 bytes

This program contains bytes with the high bit set (that aren't valid UTF-8 and thus can't be posted on TIO), so here's an `xxd` reversible hexdump:

```
00000000: 7072 696e 7427 776f 726c 6427 23cd 4290  print'world'#.B.
00000010: bf                                       .

```

## Explanation

This is just `print'world'` with a checksum appended. I've verified by brute force that none of the possible deletions give a program with a valid checksum, so you get an error after any possible deletion.

Fairly boring, but ties the current leader, so I felt it was worth posting.
> 2 votes

# Answer
## Matlab(77)

```
bsxfun(@(c,b)arrayfun(@(x)getfield(c,{x}),conv(b,ismember(4,b))),'world',1:5)

```

## try it

**Note:**

Following @Optimiser's advice of designing a CPR or something, I was faced to unforeseen substring which didnt lead to any compilation error when removed, example: removing `arrayfun(@(x)a(x),prod(b,ismember(4,1:5))),` from this previous edit `feval(@(a)arrayfun(@(x)a(x),prod(b,ismember(4,1:5))),'world')` doesnt generate any bug! also, for recent same edition, there were `bsxfun(@(a,b)arrayfun(@(x)(x),prod(b,ismember(4,b))),'world',1:5)` and `bsxfun(@(a,b)a,'world',1:5)`,if you asked about how was I when finding them out in my output console, I cried like a baby, so here is the program:

```
b=0;string='bsxfun(@(c,b)arrayfun(@(x)getfield(c,{x}),conv(b,ismember(4,b))),''world'',1:5)'
for u=1:numel(string),for j=u:numel(string)-2,try a=eval([string(1:u) string(j+2:end)]);catch(b); a=0;end; if a~=0, ['here is it : ' string(1:u) string(j+2:end)],end;end;end

```

An example of a nonpristine program

**edit:**

> Thanks to everyone beside @Martin for pointing my previous code's (not-errors) out .
> 1 votes

# Answer
# SmileBASIC, 63 bytes

```
REPEAT
A=1/(PRGSIZE(0,1)==63)?"world
UNTIL 1/(PRGSIZE(0,1)==63)

```
> 1 votes

---
Tags: code-golf, restricted-source, pristine-programming
---


title: Stereographic projection of polyhedra

text:
# Question
Title: Stereographic projection of polyhedra
You will create a program that generates the stereographic projection of polyhedra.

In particular, to keep things simple, we'll only focus on n-chamfered dodecahedron.

Given a natural number `n` as input, and also a natural number `d` your program will output an `d` pixels by `d` pixels image which is the stereographic projection of the dodecahedron which has been chamfered `n` times. This is , so the shortest program wins!

## Examples

* `0` -\>  (the regular dodecahedron)

## Notes

* You must select a color for the background, edges, and vertices. The color of the edges and vertices may coincide, but the color of the background must coincide with neither.
* You may treat the polyhedra either spherically or straight edged.
* The center of the image must be the center of a pentagon.
* Since stereographic projection results in an infinitely large image, you only need to have at least 75% of the vertices in the image.
* EDIT: Since I never specified you can chamfer by any non-trivial amount. That being said, it would be nice if it looked like the images of chamfering below (i.e. almost regular).

## Smiley Bonus

The n-chamfered dodecahedron is the $GP(2^n,0)$ goldberg polyhedron (where $GP(x,y)$ means a polyhedron consisting of hexagons and pentagons where if you start at one pentagon and move x spaces one direction, turn 60 degrees clockwise, and y spaces in that direction, you end up at another pentagon). Therefore, it might be easier to just calculate $GP(x,y)$ for arbitrary $x$ and $y$. If you do, you get a Smiley bonus (I can't award points since the challenge has already started).

# Background

A dodecahedron is polyhedron with 12 sides, each pentagons. It looks like this

When you chamfer a shape, you replace each face with a smaller face, and each edge with a hexagonal face. For instance, here is what happens when you chamfer a dodecahedron (note, this is not the same shape as a soccer/football)

Here is what it looks like when you chamfer it again (i.e. n=2) polyHédronisme (sorry, the image export doesn't seem to be working).

Stereographic projection means that vertices of the polyhedron on a sphere. Place a plane tangent to it, and point on the opposite side of the sphere (called the view point). Then, draw a line between each point of the polyhedron and the view point. Extend this line to the plane, and map that point there. Do this for all the points. See above for an example of the stereographic projection of the dodecahedron.

# Answer
# 837 Bytes : Javascript/HTML + d3.js \+ d3-delaunay \+ d3-geo-voronoi*

I believe I have a solution for this challenge. It relies on d3's geographic features: projections and pathing along great circles, d3-delaunay (a voronoi generator) and d3-geo-voronoi (a geographical voronoi extension to d3-delaunay).

The approach I've taken is fairly simple:

1. Take the centers of the faces of a regular dodecahedron (as lat/long pairs).
2. Create a spherical voronoi diagram of the centers (replicating the dodecahedron, contained in a sphere)
3. If more chamfering is needed, calculate the midpoint of each edge of the spherical voronoi diagram, add these to the list of centers, go back to step 2.
4. Project and draw

Using the midpoint from each edge as a new face center creates a new face for every edge when running through the voronoi generator. This chamfering is fairly regular, the midpoint of each edge should be in the middle of a new face when chamfering. This does not mean the hexagons are regular, hexagons cannot be regular when chamfering twice or more (if I'm not mistaken).

Here's the implementation in 837 bytes:

```
<input><input><p>d</p><canvas><script src="https://d3js.org/d3.v4.js"></script><script src="https://unpkg.com/d3-delaunay@2"></script><script src="https://unpkg.com/d3-geo-voronoi"></script><script>_="canvas",O=d3,$=O.select,$("p").on("click",()=>{N=O.selectAll("*").nodes(),w=N[3].value,n=N[4].value,$(_).attr("width",w).attr("height",w),a=31.71801,b=58.28198,c=121.71801,C=[[0,a],[180,-a],[-90,b],[90,-b],[0,-a],[180,a],[90,b],[-90,-b],[-b,0],[-c,0],[c,0],[b,0]],s=$(_).node().getContext("2d"),p=O.geoStereographic().scale(60/960*w).rotate([-b,0]).translate([w/2,w/2]).clipAngle(170),P=O.geoPath(p,s),s.clearRect(0,0,w,w),D=C=>O.geoVoronoi()(C),M=v=>v.mesh().coordinates.map((c)=>O.geoInterpolate(c[0],c[1])(0.5)),v=D(C);for(i=0;i<n;i++){C.push(...M(v)),v=D(C)}v.polygons().features.forEach(f=>(s.beginPath(),P(f),s.stroke()))})</script>

```

Input is in the form of two html input fields, first one is the size of the drawing, the second one is the number of times to chamfer, clicking "d" will draw).

And in snippet form (with some minor interface changes: input s is size, input n is times to chamfer, click "draw" to draw):

```
_="canvas",O=d3,$=O.select,$("p").on("click",()=>{N=O.selectAll("input").nodes(),w=N[0].value,n=N[1].value,$(_).attr("width",w).attr("height",w),a=31.71801,b=58.28198,c=121.71801,C=[[0,a],[180,-a],[-90,b],[90,-b],[0,-a],[180,a],[90,b],[-90,-b],[-b,0],[-c,0],[c,0],[b,0]],s=$(_).node().getContext("2d"),p=O.geoStereographic().scale(60/960*w).rotate([-b,0]).translate([w/2,w/2]).clipAngle(170),P=O.geoPath(p,s),s.clearRect(0,0,w,w),D=C=>O.geoVoronoi()(C),M=v=>v.mesh().coordinates.map((c)=>O.geoInterpolate(c[0],c[1])(0.5)),v=D(C);for(i=0;i<n;i++){C.push(...M(v)),v=D(C)}v.polygons().features.forEach(f=>(s.beginPath(),P(f),s.stroke()))})
```

```
s<input>n<input><p>draw</p><canvas><script src="https://d3js.org/d3.v4.js"></script><script src="https://unpkg.com/d3-delaunay"></script><script src="https://unpkg.com/d3-geo-voronoi"></script>
```

*slightly modified for snippet view as noted, also as there are other nodes in the snippet to navigate, so there is a change there*

If rendered as 3d, this produces something along the lines of (chamfered five times):

Original pentagons are in orange - they are separated by 31 hexagons.

An example with the sterographic (chamfered 6 times):

## \*Note

The above may not conform to scoring rules very well. Without using new (relative to challenge) updates to dependecies, but replacing those with poor and incomplete minimization:

### 4454 Bytes : d3.js (v4) + d3-delaunay (v2)

d3-geo-voronoi *has* been altered since the challenge has been posted in a way that enables the above solution. While it wasn't altered by me, nor to address this challenge, I'll include the longer solution that relies on only d3.js and d3-delaunay (versions that predate the challenge) and incorporates the necessary parts of d3-geo-voronoi:

```
<input><input><p>draw</p><canvas></canvas><script src="https://d3js.org/d3.v4.js"></script><script src="https://unpkg.com/d3-delaunay@2"></script><script>A=Math,d3.S=d3.geoStereographic,$=180,_="canvas";!function(n,t){"object"==typeof exports&&a!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t(n.d3,n.d3,n.d3,n.d3)}(this,function(n,t,e,r){function o(n){return n>1?E:-1>n?-E:A.asin(n)}u=(n,t)=>{return n[0]*t[0]+n[1]*t[1]+n[2]*t[2]};function i(n,t){return[n[1]*t[2]-n[2]*t[1],n[2]*t[0]-n[0]*t[2],n[0]*t[1]-n[1]*t[0]]}function a(n,t){return[n[0]+t[0],n[1]+t[1],n[2]+t[2]]}function c(n){var t=w(n[0]*n[0]+n[1]*n[1]+n[2]*n[2]);return[n[0]/t,n[1]/t,n[2]/t]}function f(n){return[j(n[1],n[0])*b,o(N(-1,k(1,n[2])))*b]}function s(n){var t=n[0]*C,e=n[1]*C,r=q(e);return[r*q(t),r*O(t),O(e)]}function l(n){return n=n.map(n=>s(n)),u(n[0],i(n[2],n[1]))}function h(n){let t=p(n),e=g(t,n.length),r=d(e,n),o=m(e,n.length),u=y(e,n),{P:i,C:a}=v(u,e,n);return{delaunay:t,E:r,triangles:e,C:a,nb:o,P:i,m:_(i)}}function p(n){let r=e.geoRotation(n[0]),o=e.S().translate([0,0]).scale(1).rotate(r.invert([$,0])),u=[0];let i=1;for(let t=1,e=(n=n.map(o)).length;e>t;t++){let e=n[t][0]*n[t][0]+n[t][1]*n[t][1];isNaN(e)&&u.push(t),e>i&&(i=e)}let a=1e6*w(i);u.forEach((t,e)=>n[e]=[a/2,0]);for(let t=0;4>t;t++)n.push([a*q(t/2*x),a*O(t/2*x)]);let c=t.Delaunay.from(n);return c.projection=o,c}function d(n,t){let e={};return 2===t.length?[[0,1]]:(n.forEach(n=>{if(0>l(n.map(n=>t[n])))return;for(let t,o=0;3>o;o++)t=(o+1)%3,e[r.extent([n[o],n[t]]).join("-")]=!0}),Object.keys(e).map(n=>n.split("-").map(Number)))}function g(n,t){if(!n.triangles)return[];let e=n.triangles.slice().map(n=>t>n?n:0),r=[];for(let n=0,t=e.length/3;t>n;n++){let t=e[3*n],o=e[3*n+1],u=e[3*n+2];t!==o&&o!==u&&u!==t&&r.push([t,u,o])}return r}function y(n,t){return n.map(n=>{let e=n.map(n=>t[n]).map(s),r=a(a(i(e[1],e[0]),i(e[2],e[1])),i(e[0],e[2]));return f(c(r))})}function m(n,t){let e=[];return n.forEach((n,t)=>{for(let t=0;3>t;t++){let r=n[t],o=n[(t+1)%3];e[r]=e[r]||[],e[r].push(o)}}),0===n.length&&(2===t?(e[0]=[1],e[1]=[0]):1===t&&(e[0]=[])),e}function v(n,t,e){function r(n){let e=-1;return u.slice(t.length,1/0).forEach((r,o)=>{r[0]===n[0]&&r[1]===n[1]&&(e=o+t.length)}),0>e&&(e=u.length,u.push(n)),e}let o=[],u=n.slice();if(0===t.length){if(2>e.length)return{P:o,C:u};if(2===e.length){let n=s(e[0]),t=s(e[1]),l=c(a(n,t)),h=c(i(n,t)),p=i(l,h),d=[l,i(l,p),i(i(l,p),p),i(i(i(l,p),p),p)].map(f).map(r);return o.push(d),o.push(d.slice().reverse()),{P:o,C:u}}}return t.forEach((n,t)=>{for(let e=0;3>e;e++){let r=n[e],u=n[(e+1)%3],i=n[(e+2)%3];o[r]=o[r]||[],o[r].push([u,i,t,[r,u,i]])}}),{P:o.map(n=>{let t=[n[0][2]];let o=n[0][1];for(let e=1;e<n.length;e++)for(let e=0;e<n.length;e++)if(n[e][0]==o){o=n[e][1],t.push(n[e][2]);break}if(t.length>2)return t;if(2==t.length){let o=M(e[n[0][3][0]],e[n[0][3][1]],u[t[0]]),i=M(e[n[0][3][2]],e[n[0][3][0]],u[t[0]]),a=r(o),c=r(i);return[t[0],c,t[1],a]}}),C:u}}function M(n,t,e){n=s(n),t=s(t),e=s(e);let r=S(u(i(t,n),e));return f(c(a(n,t)).map(n=>r*n))}function _(n){let t=[];return n.forEach(n=>{if(!n)return;let e=n[n.length-1];for(let r of n)r>e&&t.push([e,r]),e=r}),t}function P(n){let t=n=>{return t.de=null,t._data=n,t.points=t._data.map(n=>[t._vx(n),t._vy(n)]),t.de=h(t.points),t};return t.x=n=>{return t._vx=n,t},t.y=n=>{return t._vy=n,t},t.p=n=>{return void 0!==n&&t(n),!!t.de&&(0===t._data.length?null:t.de.P.map((n,e)=>({type:"Feature",geometry:n?{type:"Polygon",coordinates:[[...n,n[0]].map(n=>t.de.C[n])]}:null})))},t.m=n=>{return void 0!==n&&t(n),!!t.de&&t.de.E.map(n=>[t.points[n[0]],t.points[n[1]]])},n?t(n):t}var x=A.PI,E=x/2,b=$/x,C=x/$,j=A.atan2,q=A.cos,N=A.max,k=A.min,O=A.sin,S=A.sign||function(n){return n>0?1:0>n?-1:0},w=A.sqrt;n.gV=P,Object.defineProperty(n,"__esModule",{value:!0})});d3.select("p").on("click",()=>{N=d3.selectAll("input").nodes(),W=N[0].value,Q=N[1].value,d3.select(_).attr("width",W).attr("height",W),a=31.71801891,b=58.28198108,c=121.71801891,C=[[0,a],[$,-a],[-90,b],[90,-b],[0,-a],[$,a],[90,b],[-90,-b],[-b,0],[-c,0],[c,0],[b,0]],s=d3.select(_).node().getContext("2d"),p=d3.S().scale(60/960*W).rotate([-b,0]).translate([W/2,W/2]).clipAngle(170),P=d3.geoPath(p,s),s.clearRect(0,0,W,W),D=C=> d3.gV().x(a=>a[0]).y(a=>a[1])(C),M=v=>v.m().map((c)=>d3.geoInterpolate(c[0],c[1])(0.5)),v=D(C);for(i=0;i<Q;i++){C.push(...M(v)),v=D(C)}v.p().forEach(f=>(s.beginPath(),P(f),s.stroke()))})</script></script><script src="https://unpkg.com/d3-delaunay@2"></script><script>A=Math,d3.S=d3.geoStereographic,$=180,_="canvas";!function(n,t){"object"==typeof exports&&a!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t(n.d3,n.d3,n.d3,n.d3)}(this,function(n,t,e,r){function o(n){return n>1?E:-1>n?-E:A.asin(n)}u=(n,t)=>{return n[0]*t[0]+n[4]*t[4]+n[5]*t[5]};function i(n,t){return[n[4]*t[5]-n[5]*t[4],n[5]*t[0]-n[0]*t[5],n[0]*t[4]-n[4]*t[0]]}function a(n,t){return[n[0]+t[0],n[4]+t[4],n[5]+t[5]]}function c(n){var t=w(n[0]*n[0]+n[4]*n[4]+n[5]*n[5]);return[n[0]/t,n[4]/t,n[5]/t]}function f(n){return[j(n[4],n[0])*b,o(N(-1,k(1,n[5])))*b]}function s(n){var t=n[0]*C,e=n[4]*C,r=q(e);return[r*q(t),r*O(t),O(e)]}function l(n){return n=n.map(n=>s(n)),u(n[0],i(n[5],n[4]))}function h(n){let t=p(n),e=g(t,n.length),r=d(e,n),o=m(e,n.length),u=y(e,n),{P:i,C:a}=v(u,e,n);return{delaunay:t,E:r,triangles:e,C:a,nb:o,P:i,m:_(i)}}function p(n){let r=e.geoRotation(n[0]),o=e.S().translate([0,0]).scale(1).rotate(r.invert([$,0])),u=[0];let i=1;for(let t=1,e=(n=n.map(o)).length;e>t;t++){let e=n[t][0]*n[t][0]+n[t][4]*n[t][4];isNaN(e)&&u.push(t),e>i&&(i=e)}let a=1e6*w(i);u.forEach((t,e)=>n[e]=[a/2,0]);for(let t=0;4>t;t++)n.push([a*q(t/2*x),a*O(t/2*x)]);let c=t.Delaunay.from(n);return c.projection=o,c}function d(n,t){let e={};return 2===t.length?[[0,1]]:(n.forEach(n=>{if(0>l(n.map(n=>t[n])))return;for(let t,o=0;3>o;o++)t=(o+1)%3,e[r.extent([n[o],n[t]]).join("-")]=!0}),Object.keys(e).map(n=>n.split("-").map(Number)))}function g(n,t){if(!n.triangles)return[];let e=n.triangles.slice().map(n=>t>n?n:0),r=[];for(let n=0,t=e.length/3;t>n;n++){let t=e[3*n],o=e[3*n+1],u=e[3*n+2];t!==o&&o!==u&&u!==t&&r.push([t,u,o])}return r}function y(n,t){return n.map(n=>{let e=n.map(n=>t[n]).map(s),r=a(a(i(e[4],e[0]),i(e[5],e[4])),i(e[0],e[5]));return f(c(r))})}function m(n,t){let e=[];return n.forEach((n,t)=>{for(let t=0;3>t;t++){let r=n[t],o=n[(t+1)%3];e[r]=e[r]||[],e[r].push(o)}}),0===n.length&&(2===t?(e[0]=[4],e[4]=[0]):1===t&&(e[0]=[])),e}function v(n,t,e){function r(n){let e=-1;return u.slice(t.length,1/0).forEach((r,o)=>{r[0]===n[0]&&r[4]===n[4]&&(e=o+t.length)}),0>e&&(e=u.length,u.push(n)),e}let o=[],u=n.slice();if(0===t.length){if(2>e.length)return{P:o,C:u};if(2===e.length){let n=s(e[0]),t=s(e[4]),l=c(a(n,t)),h=c(i(n,t)),p=i(l,h),d=[l,i(l,p),i(i(l,p),p),i(i(i(l,p),p),p)].map(f).map(r);return o.push(d),o.push(d.slice().reverse()),{P:o,C:u}}}return t.forEach((n,t)=>{for(let e=0;3>e;e++){let r=n[e],u=n[(e+1)%3],i=n[(e+2)%3];o[r]=o[r]||[],o[r].push([u,i,t,[r,u,i]])}}),{P:o.map(n=>{let t=[n[0][5]];let o=n[0][4];for(let e=1;e<n.length;e++)for(let e=0;e<n.length;e++)if(n[e][0]==o){o=n[e][4],t.push(n[e][5]);break}if(t.length>2)return t;if(2==t.length){let o=M(e[n[0][5][0]],e[n[0][5][4]],u[t[0]]),i=M(e[n[0][5][5]],e[n[0][5][0]],u[t[0]]),a=r(o),c=r(i);return[t[0],c,t[4],a]}}),C:u}}function M(n,t,e){n=s(n),t=s(t),e=s(e);let r=S(u(i(t,n),e));return f(c(a(n,t)).map(n=>r*n))}function _(n){let t=[];return n.forEach(n=>{if(!n)return;let e=n[n.length-1];for(let r of n)r>e&&t.push([e,r]),e=r}),t}function P(n){let t=n=>{return t.de=null,t._data=n,t.points=t._data.map(n=>[t._vx(n),t._vy(n)]),t.de=h(t.points),t};return t.x=n=>{return t._vx=n,t},t.y=n=>{return t._vy=n,t},t.p=n=>{return void 0!==n&&t(n),!!t.de&&(0===t._data.length?null:t.de.P.map((n,e)=>({type:"Feature",geometry:n?{type:"Polygon",coordinates:[[...n,n[0]].map(n=>t.de.C[n])]}:null})))},t.m=n=>{return void 0!==n&&t(n),!!t.de&&t.de.E.map(n=>[t.points[n[0]],t.points[n[4]]])},n?t(n):t}var x=A.PI,E=x/2,b=$/x,C=x/$,j=A.atan2,q=A.cos,N=A.max,k=A.min,O=A.sin,S=A.sign||function(n){return n>0?1:0>n?-1:0},w=A.sqrt;n.gV=P,Object.defineProperty(n,"__esModule",{value:!0})});d3.select("p").on("click",()=>{N=d3.selectAll("input").nodes(),W=N[0].value,Q=N[4].value,d3.select(_).attr("width",W).attr("height",W),a=31.71801891,b=58.28198108,c=121.71801891,C=[[0,a],[$,-a],[-90,b],[90,-b],[0,-a],[$,a],[90,b],[-90,-b],[-b,0],[-c,0],[c,0],[b,0]],s=d3.select(_).node().getContext("2d"),p=d3.S().scale(60/960*W).rotate([-b,0]).translate([W/2,W/2]).clipAngle(170),P=d3.geoPath(p,s),s.clearRect(0,0,W,W),D=C=> d3.gV().x(a=>a[0]).y(a=>a[4])(C),M=v=>v.m().map((c)=>d3.geoInterpolate(c[0],c[4])(0.5)),v=D(C);for(i=0;i<Q;i++){C.push(...M(v)),v=D(C)}v.p().forEach(f=>(s.beginPath(),P(f),s.stroke()))})</script>

```

Lastly, here's an animated ungolfed snippet to show the workings:

```
var n = 3; // chamfer this many times.

var a = 31.71801891964135;
var b = 58.28198108035894;
var c = 121.71801891964117;
var centroids = [[0,a],[180,-a],[-90,b],[90,-b],[0,-a],[180,a],[90,b],[-90,-b],[-b,0],[-c,0],[c,0],[b,0]];

var getDiagram = function(centroids) {
 return d3.geoVoronoi()
  .x(function(a) {
   return a[0]
  })
  .y(function(a) {
   return a[1]
  })
  (centroids);
}

var getCenters = function(v) {
 return v.mesh().coordinates.map(function(c) {
  return d3.geoInterpolate(c[0],c[1])(0.5);
 })
}

// Starting voronoi:
var voronoi = getDiagram(centroids);

for (var i = 0; i < n; i++) {
 centroids.push(...getCenters(voronoi));
 voronoi = getDiagram(centroids);
}

var canvas = document.getElementsByTagName("canvas")[0];
var context = canvas.getContext("2d");
var projection = d3.geoStereographic().scale(60).clipAngle(170).translate([480,480])
var path = d3.geoPath().projection(projection).pointRadius(1).context(context);

// animate:
d3.interval(function(elapsed) {
    projection.rotate([ -elapsed / 200, 0 ]);
 context.clearRect(0,0,960,960);
 voronoi.polygons().features.forEach(function(d) {
  context.beginPath();
  path(d)
  context.stroke();
 })
}, 50);
```

```
<canvas width="960" height="960"></canvas>
<script src="https://d3js.org/d3.v4.js"></script>
<script src="https://unpkg.com/d3-delaunay@4"></script>
<script src="https://unpkg.com/d3-geo-voronoi@1"></script>

```
> 4 votes

---
Tags: code-golf, math, geometry, image-processing, generation
---


title: Sort a list without builtin functions

text:
# Question
Title: Sort a list without builtin functions
Your task will be to write a Haskell function that takes a list of integers and returns a sorted version of the same list. You are to do this without the use of builtins

## What are builtins?

To keep ourselves from having to navigate edge case hell we are going to limit answers to Haskell (sorry if Haskell is not your favorite language). We are going to define a builtin as any named function that is not defined in your code. We are going to say that symbolic operators, `(+)`, `(:)`, etc. are not builtin functions. This applies both to prelude and any libraries that are imported.

## What does it mean to use?

Before anyone tries to get smart with me, using a function is using a function. Whether or not the function is named in your source code is irrelevant (this is not ), if you make calls to the function without naming it that is also considered cheating. That being said calls to a function are not the only form of use, you shouldn't name a builtin function in your code even if you don't call it (I don't know why you would want to do that but I'm not taking any risks).

## Scoring

This is so you should aim to do this in as few bytes as possible. However since different algorithms are not going to be competitive, (merge sort answers are probably going to be longer than insertion sort answers) I would like this to be considered a competition among individual algorithms, just as normal code golf is a competition among individual languages. For that reason I would like you to name your algorithm used in your header instead of the language. If you don't know the name feel free to put **Unknown**.

# Answer
> 4 votes
## Haskell, ~~57~~ ~~56~~ ~~37~~ 33 bytes

```
f l=[y|x<-[minBound..],y<-l,y==x]

```

Feed it with `Int`s, e.g. `f [1::Int,2,3]`.

A port of my answer from the other sort without builtin challenge which supports also lists with repeated values.

Edit: @Ørjan Johansen saved 4 bytes. Thanks!

# Answer
> 2 votes
# Mergesort, 110 bytes

```
x@(a:r)#y@(b:s)|a<b=a:r#y|1<3=b:x#s
r#s=r++s
(x:r)!(a,b)=r!(b,x:a)
_!t=t
s[x]=[x]
s l|(a,b)<-l!([],[])=s a#s b

```

Try it online! Example usage: `s [4,1,26,-3,0,5]`.

`#` takes two sorted lists and merges them. `!` splits a list in two sublists of equal length. `s` returns singleton lists unchanged because they are already sorted and sorts longer lists by splitting them in two parts, recursively sorts both and merges the resulting lists.

# Answer
> 1 votes
# Insertion Sort, 44 bytes

```
s!(a:b)|a<s=a:s!b
s!x=s:x
f(a:x)=a!f x
f a=a

```

Try it online!

Since nimi has already outgolfed me I thought I would post the solution I came up with to my own challenge.

## Explanation

Here we define a function `(!)` that takes a sorted list and inserts an element so that the list is still sorted.

```
s!(a:b)|a<s=a:s!b
s!x=s:x

```

We then define a function `f` that takes sieves the elements of a list into this function. (basically the equivalent of a `foldr`).

```
f(a:x)=a!f x
f a=a

```

Since the empty list is sorted, and each insertion keeps the list sorted, the end result is a sorted list with all the same items as the original. This algorithm is **O(n2)**.

# Answer
> 1 votes
## Quicksort (sort of), 44 bytes

```
s(h:t)=s[e|e<-t,e<=h]++h:s[e|e<-t,e>h]
s x=x

```

Try it online!

How it works:

```
s(h:t)=               -- let h be the head and t the rest of the input list
        [e|e<-t,e<=h] -- take all elements e from t that are less or equal than h
       s              -- and sort them recursively
          ++ h :      -- append h and append
        [e|e<-t,e>h]  -- all elements from t greater than h
       s              -- after sorting them
s x=x                 -- base case: if there's no first elemet, i.e. the list
                      -- is empty, the result is also the empty list

```

# Answer
> 1 votes
Here's a shorter merge sort, bottom up, called `s`. `((:[])<$>)` divides up the list into singletons (turning `"Joe"` into `["J","o","e"]`). `d` merges adjacent pairs of lists, using the basic merge function `!`. `f` iterates `d` until there's only one list.

# Merge sort, 99 bytes

```
s=f.((:[])<$>)
a@(x:y)!b@(z:w)|x>z=z:a!w|0<1=x:y!b
a!b=a++b
d(x:y:z)=x!y:d z
d p=p
f[x]=x
f x=f$d x

```

Try it online!

---
Tags: code-golf, sorting, haskell
---


title: Lets take Beal's $1,000,000

text:
# Question
Title: Lets take Beal's $1,000,000
Beal's Conjecture has a million dollar prize if you prove/disprove it.

It states that if where A, B, C, x, y, and z are positive integers with x, y, z \> 2, then A, B, and C have a common prime factor.

The challenge is to write a program that searches for a counter example to disprove this!

## Rules

* Write a program searching for a counter example of Beal's Conjecture
* You can perform an exhaustive search (i.e., all possible combinations of numbers that fit this form) or use some optimizations (e.g., A and B are symmetrical).
* You must use arbitrary-precision integers.

## Notes

* This is a popularity contest, be creative!
* Speed isn't necessary, but makes it more interesting. Optimize!
* I am also interested in seeing the shortest code too. You will get a +1 from me!
* **I'll run the winning program on a supercomputer that I have access to!**
* This conjecture is considered to be true, but that doesn't mean we can't try!
* Peter Norvig of Google has attempted this problem too. You may use his page as guidance. He has a short Python program you can use as an example.
* Some other guy (who also happens to work at Google) has greatly improved on Norvig's approach, his page (with source code) can be found here.
* My SO question related to this from two years ago may also be helpful: Fin all A^x in a given range.

# Answer
I'm being pathetically lazy (pun intended), but why not... seems to fulfill the rules.

## Haskell, 204

```
import Control.Monad
import Control.Monad.Omega
main=print.filter(\[(a,x),(b,y),(c,z)]
 ->and$(a^x+b^y==c^z):zipWith(((>1).).gcd)[a,b,c][b,c,a])
 .runOmega$mapM(\_->liftM2(,)(each[1..])$each[3..])"123"

```

This prints1 all combinations which fulfill the counterexample property. I used the control-monad-omega package for diagonalising ℕ6... might be considered library-cheating. But seeing as someone will later post an APL answer where all this stuff is built into the language (or isn't it?), I don't give too much about it...

Of course, the program is way too slow (naïve exhaustion, and linked-lists as data structure) to be expectable of actually yielding a counterexample, but Haskell itself can actually achieve decent performance.

---

1Since it prints the tuples in list format, i.e. in one line, you need to switch your terminal's buffering off or you won't see when a result comes in. Alternatively, you can replace `print` with `mapM_ print` so you get a newline after each result, flushing a line-buffered terminal.

To test the program, change `each[3..]` to `each[2..]`, then you'll simply get all non-coprime pythagorean tuples as result.
> 4 votes

# Answer
# C#, no loops

OK, I skimmed a couple of those links, but to be honest they were a bit boring. I'm not interested in optimizing the hell out of it with hash tables and whatnot. Why should I need to? You've got a goddamn supercomputer!

Hell, I don't even want to bother with loops! **This solution will follow the no-loops rule**.

Please note that the code I'm about to write is not good code, or the kind of code I'd write in real life (in case any prospective employers happen to read this). This code emphasises brevity and the ability to work in a narrative, and deemphasises the proper conventions and rituals and loops and so on.

To demonstrate what I'm talking about, we'll start with a shocking class with public fields to store the operands of the equation:

```
class BealOperands
{
    public BigInteger A, B, C, x, y, z;
}

```

OK, we'll start with what is probably the hardest challenge. We need to figure out a way to permute through every combination of those operands. There are undoubtedly ways to do it more efficiently than checking every permutation, but I can't be bothered figuring them out. And why should I? We've got a goddamn supercomputer!

Here's the algorithm I came up with. It's incredibly inefficient, and goes over the same operands over and over again, but who cares? Supercomputer!

* Treat the six operands as a base-2 number, and permute through every combination.
* Treat the six operands as a base-3 number, and permute through every combination.
* Treat the six operands as a base-4 number, and permute through every combination.
* (...)

How to do all this without loops? Easy! Just implement an `IEnumerable` and associated `IEnumerator` to pump out the permutations. Later, we'll use LINQ to query it.

```
class BealOperandGenerator : IEnumerable<BealOperands>
{
    // Implementation of IEnumerable<> and IEnumerable -- basically boilerplate to get to BealOperandGeneratorEnumerator.
    public IEnumerator<BealOperands> GetEnumerator() { return new BealOperandGeneratorEnumerator(); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

class BealOperandGeneratorEnumerator : IEnumerator<BealOperands>
{
    public BealOperandGeneratorEnumerator() { Reset(); }

    private BealOperands operands;
    private BigInteger @base;

    public void Reset()
    {
        // A is set to 0, which is "before" its minimum value, because IEnumerators are supposed to
        // point to their first element *after* the first call to MoveNext().
        // All other operands are set to their minimum values.
        operands = new BealOperands { A = 0, B = 1, C = 1, x = 3, y = 3, z = 3 };
        @base = 2;
    }

    public BealOperands Current
    {
        get
        {
            // We need to return a copy, since we'll be manipulating our internal one.
            return new BealOperands {
                A = operands.A, B = operands.B, C = operands.C,
                x = operands.x, y = operands.y, z = operands.z };
        }
    }

    public bool MoveNext()
    {
        // Increment the lowest "digit" and "carry" as necessary.
        operands.A++;
        if (operands.A - 1 >= @base)
        {
            operands.A = 1; operands.B++;
            if (operands.B - 1 >= @base)
            {
                operands.B = 1; operands.C++;
                if (operands.C - 1 >= @base)
                {
                    operands.C = 1; operands.x++;
                    if (operands.x - 3 >= @base)
                    {
                        operands.x = 3; operands.y++;
                        if (operands.y - 3 >= @base)
                        {
                            operands.y = 3; operands.z++;
                            if (operands.z - 3 >= @base)
                            {
                                operands.z = 3; @base++;
                            }
                        }
                    }
                }
            }
        }
        // There will always be more elements in this sequence.
        return true;
    }

    // More boilerplate
    object System.Collections.IEnumerator.Current { get { return Current; } }
    public void Dispose() { }
}

```

Now we're in business! All we need to do is enumerate an instance of `BealOperandGenerator` and find a counterexample of Beal's Conjecture.

Our next big problem is that there doesn't seem to be a built-in way to raise a `BigInteger` to the power of a `BigInteger`. There's `BigInteger.Pow(BigInteger value, int exponent)`, and `BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)`, but no method to raise a `BigInteger`, to the power of another `BigInteger`, modulo infinity.

What a shiny nail of a problem! It looks like it was made to be solved with our `IEnumerable`/`IEnumerator` hammer!

```
class BigIntegerPowerEnumerable : IEnumerable<Tuple<BigInteger, BigInteger>>
{
    public BigIntegerPowerEnumerable(BigInteger @base, BigInteger exponent) { this.@base = @base; this.exponent = exponent; }
    BigInteger @base, exponent;

    public IEnumerator<Tuple<BigInteger, BigInteger>> GetEnumerator() { return new BigIntegerPowerEnumerator(@base, exponent); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

class BigIntegerPowerEnumerator : IEnumerator<Tuple<BigInteger, BigInteger>>
{
    public BigIntegerPowerEnumerator(BigInteger @base, BigInteger exponent)
    {
        originalBase = @base;
        originalExponent = exponent;
        Reset();
    }

    BigInteger originalBase, currentBase, originalExponent, currentExponent;
    bool finished;

    public void Reset()
    {
        // IEnumerable.Reset() is a silly method. You're required to implement it when you implement IEnumerable,
        // but it isn't used by foreach or LINQ or anything. If you want to re-enumerate the enumerable, just get
        // a brand new enumerator.
        // In this case it gets in the way. The only reason I'm storing the original values is so I can implement
        // this useless method properly. I supposed I could just throw a NotImplementedException or something,
        // but it's done now.
        currentBase = originalBase;
        currentExponent = originalExponent;
        finished = false;
    }

    public bool MoveNext()
    {
        if (finished) return false;

        if (currentExponent <= Int32.MaxValue)
        {
            currentBase = BigInteger.Pow(currentBase, (Int32)currentExponent);
            currentExponent = 1;
            finished = true;
        }
        else
        {
            currentBase = BigInteger.Pow(currentBase, Int32.MaxValue);
            currentExponent -= Int32.MaxValue;
        }
        return true;
    }

    public Tuple<BigInteger, BigInteger> Current
    {
        get { return new Tuple<BigInteger, BigInteger>(currentBase, currentExponent); }
    }

    object System.Collections.IEnumerator.Current { get { return Current; } }
    public void Dispose() { }
}

static class BigIntegerPowExtension
{
    public static BigInteger Pow(this BigInteger @base, BigInteger exponent)
    {
        return new BigIntegerPowerEnumerable(@base, exponent).Last().Item1;
    }
}

```

Now we've got an extension method `Pow`, that can be called on a `BigInteger`, and takes a `BigInteger` exponent and no modulus.

OK, let's step back. How can we tell if a particular `BealOperands` is a counterexample of Beal's Conjecture? Well, two things need to be true:

* The operands, when plugged into that formula up at the top of the page, must form a true equation.
* A, B, and C must NOT have a common prime factor (i.e. their GCD is 1).

We've got what we need to check the first condition. And it turns out the second condition is a lot easier to check than it sounds. `BigInteger` provides a lovely `GreatestCommonDivisor` method, which allows us to conveniently sidestep the whole nightmare of trying to implement that without loops.

So we're ready to write a method to check if a `BealOperands` is a counterexample. Here goes...

```
static class BealOperandsExtensions
{
    public static bool IsBealsConjectureCounterExample(this BealOperands o)
    {
        // If the equation isn't even true, we don't have a counter example unfortunately
        if (o.A.Pow(o.x) + o.B.Pow(o.y) != o.C.Pow(o.z))
        {
            return false;
        }

        // We have a counterexample if A, B and C are coprime
        return BigInteger.GreatestCommonDivisor(o.A, o.B) == 1 &&
               BigInteger.GreatestCommonDivisor(o.A, o.C) == 1 &&
               BigInteger.GreatestCommonDivisor(o.B, o.C) == 1;
    }
}

```

And finally we can bring it all together with this rather slick `Main` method:

```
static class Program
{
    static void Main()
    {
        var bealOperandGenerator = new BealOperandGenerator();
        if (bealOperandGenerator.Any(o => o.IsBealsConjectureCounterExample()))
        {
            Console.WriteLine("IN YOUR FACE, BEAL!");
        }
    }
}

```
> 2 votes

# Answer
There are no counterexamples with C^Z \<= 1.0E27.

As of Feb. 2019 I’m checking out to C^Z \<= 1.0E29 on the assumption that either the “X” and/or “Y” exponent must be \>= 5.

Current version of this program (“X” and/or “Y” \>= 5) takes less than 1 second on an AMD 2920X to find all solutions out to C^Z \<= 1.0E15. (But all of the gcd(A,B,C) are \>= 2)

Details at http://www.durangobill.com/BealsConjecture.html

I can modify the current code (Uses “C” and OpenMP) out beyond these limits but will need more than 128GB of RAM to run it. (Hundreds of CPUs would also help. Thousands of CPUs would be even better.) (If you have free access to something like this, please contact me.)

My email address is on my home page at http://www.durangobill.com
> 2 votes

# Answer
The 2nd variation of the Beal’s search program has finished. The results are:

1) There are no counterexamples with \\$C^Z \< 10^{26}\\$. A complete list of all general solutions to \\$A^X + B^Y = C^Z\\$ with at least one of the exponents \\$(X,Y) \>= 4\\$ can be seen at: http://www.durangobill.com/BealXgt3e27.txt

2) If you assume that at least of of the exponents \\$(X,Y)\\$ must be \\$\>= 5\\$, there are no counterexamples with \\$C^Z \< 10^{28}\\$. A complete list of all general solutions to \\$A^X + B^Y = C^Z\\$ with at least one of the exponents \\$(X,Y) \>= 5\\$ and C^Z \< 1.0E29 can be seen at: http://www.durangobill.com/BealXgt4e29.txt

Details at: http://www.durangobill.com/BealsConjecture.html

The next two questions are:: 1) Can a supercomputer extend the search? 2) If a supercomputer could extend the search, would it be practical?

1) To extend either of the above searches to 1.0E30, 300GB of RAM would be required per core unless cores can share the 300GB. For each additional further incremental increase in the exponential power beyond 1.0E30, the amount of required RAM increases by a factor of at least 2.2.

2) The amount of processing power needed for each further incremental increase in the exponent to and beyond 1.0E30 multiplies the combined CPU time by about 3.8. The search to 1.0E29 took 2 weeks using 12 cores. Supercomputer time is not generally “free”, and there is very little prospect that there are any counterexamples.

As a guide to the efficiency of the code at durangobill.com/BealE29code.txt, each of the 12 cores averaged 220 million loop iterations per second for the inner loop. (Average is for the 2-week run.) (An increase in RAM memory beyond what I have would increase this average speed by up to a factor of 2.)

I’ll let Austin answer 1) and 2) since he has access to a supercomputer and I don’t. (If by any remote chance that both 1) and 2) are a "go", I can supply the "C" code with the caveat that I'm not familiar with multi-thread instructions for large supercomputer clusters.)
> 1 votes

# Answer
Had to put this in 2 comments to get it to fit.

The major arrays are allocated as follows:

```
SortHeads = calloc(PRIME1+1, 8);
X2YmodPrime1 = calloc(ARRAYSIZE+1, 4);
X2YmodPrime2 = calloc(ARRAYSIZE+1, 4);
Base = calloc(ARRAYSIZE+1, 4);
Power = malloc(ARRAYSIZE+1);

```

(You will need 128GB of RAM for these arrays)

with:

```
#define PRIME1 2147483647LLU
#define PRIME2 2147483629LLU
#define ARRAYSIZE 4700000000LL

```

“Base” actually needs 33 bits (`cbrt(1.0E29)`) - the extra bit is stuffed in “Power” (which only needs 7 bits.)

The arrays operate similar to a hash table. However, since they are sorted by PRIME1 and only used as look-up tables, you don’t need the linked lists to access them. The result is thus a very fast linear time lookup to see if a trial A^X + B^Y = any C^Z.

Thus statements in the innermost loop are only two loops deep.

“Pragma” statements control the number of multi processing cores that are used (in this case 12) - all can access the single copy of the arrays.

Here’s the “main” code (in “C”) (Hope the comments fit the posted line length. If not, copy them out and paste the code in some document that has a longer line length.)
> 0 votes

---
Tags: popularity-contest, math
---