# Question
Title: sort and restore a set of bytes in optimal form
**Challenge**

For any given input **Y** of length \>= 1024 bytes:

* sort in ascending or descending order -- your choice
* generate output **Q**, where **Q** = \[*sorted data*\] + \[*restore information*\]
* restore **Y** using **Q** as input

**Sorting Example**

```
 input: [2, 5, 119, 0, 1, 223, 0, 118, ...]
output: [0, 0, 1, 2, 5, 118, 119, 223, ...] + [restore information]

```

**Restore Example**

```
 input: [0, 0, 1, 2, 5, 118, 119, 223, ...] + [restore information]
output: [2, 5, 119, 0, 1, 223, 0, 118, ...]

```

**Winning**

The program that generates the least amount of information in order to restore to original state wins, however it must work within a reasonable amount of time on modern hardware, less than 10 minutes.

**UPDATE 1**

You may use any third party libraries that are open-source if you so desire.

**UPDATE 2**

The \[restore information\] size is measured in bytes, it's your choice what it contains.

**UPDATE 3**

In case it's not yet clear, the input **Y** is a stream of bytes, you shouldn't care what it contains, all you care is to sort the values of the bytes in the order you prefer while also generating the necessary data in order to restore to **Y** from **Q**.

# Answer
> 7 votes
## Python

The restore information is just the original list. *n* bytes of restore information for an *n* byte list.

```
def sort(Y):
  return (sorted(Y), Y)

def restore(Q):
  return Q[1]

```

# Answer
> 2 votes
# Scala + Arithmetic coding

Once we sort the data, all we're left with is the frequencies of the bytes within the original. Conveniently, this is exactly what we need for efficient adaptive arithmetic coding. We use arithmetic coding on the frequencies of the remaining elements of the data. I suspect this is information theoretically optimal, for random data.

I've used nayuki's arithmetic coding library.

```
import nayuki.arithcode._
import java.io.ByteArrayOutputStream
import java.io.ByteArrayInputStream
import java.nio.charset.StandardCharsets.UTF_8

object Unsort {
  def mkTable(data: Array[Byte]) = {
    val frequencyMap = data.groupBy(identity).mapValues(_.size)
    val frequencyArray = (0 to 255).map(i => frequencyMap.getOrElse(i.toByte, 0)).toArray
    new RemainingFrequencies(frequencyArray)
  }

  def sort(data: Array[Byte]) = {
    val freqTable = mkTable(data)
    val output = new ByteArrayOutputStream
    val bitOutput = new BitOutputStream(output)
    val encoder = new ArithmeticEncoder(bitOutput)
    for (b <- data) {
      val i = b.toInt & 0xff
      encoder.write(freqTable, i)
      freqTable.decrement(i)
    }
    encoder.finish()
    bitOutput.close()
    (data.sorted, output.toByteArray)
  }

  def unsort(dataAndMetadata: (Array[Byte], Array[Byte])) = {
    val (data, metadata) = dataAndMetadata
    val freqTable = mkTable(data)
    val input = new ByteArrayInputStream(metadata)
    val bitInput = new BitInputStream(input)
    val decoder = new ArithmeticDecoder(bitInput)
    (for (_ <- 0 until data.length) yield {
      val x = decoder.read(freqTable)
      freqTable.decrement(x)
      x.toByte
    }).toArray
  }

  def main(args: Array[String]) = {
    val stringData = args.reduce(_ + " " +_)
    val data = stringData.getBytes(UTF_8)
    val (sorted, metadata) = sort(data)
    val unsorted = unsort((sorted, metadata))
    val unsortedString = new String(unsorted, UTF_8)
    println(s"""Received "${stringData}"""")
    println(s"""Sorted to ${sorted.toList} + ${metadata.toList}""")
    println(s"""(${sorted.length} bytes of data, ${metadata.length} bytes of metadata)""")
    println(s"""Unsorted to "$unsortedString"""")
  }
}

class RemainingFrequencies(private val frequencies: Array[Int]) extends FrequencyTable {
  override val getSymbolLimit = 256
  override def get(symbol: Int) = frequencies(symbol)
  override def set(symbol: Int, freq: Int) = ???
  override def increment(symbol: Int) = ???
  override def getTotal = frequencies.sum
  override def getLow(symbol: Int) = frequencies.slice(0, symbol).sum
  override def getHigh(symbol: Int) = frequencies.slice(0, symbol + 1).sum
  def decrement(symbol: Int) = frequencies(symbol) -= 1
}

```

As an example of the output, here's what happens when we run it against the first paragraph of Franz Kafka's Metamorphosis:

```
Received "One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin. He lay on his armour-like back, and if he lifted his head a little he could see his brown belly, slightly domed and divided by arches into stiff sections. The bedding was hardly able to cover it and seemed ready to slide off any moment. His many legs, pitifully thin compared with the size of the rest of him, waved about helplessly as he looked."
Sorted to List(32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 44, 44, 44, 44, 44, 44, 45, 46, 46, 46, 46, 71, 72, 72, 79, 83, 84, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 97, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 99, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 101, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 102, 103, 103, 103, 103, 103, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 104, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 105, 107, 107, 107, 107, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 109, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 112, 112, 112, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 114, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 115, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 116, 117, 117, 117, 117, 117, 117, 118, 118, 118, 118, 119, 119, 119, 119, 119, 119, 121, 121, 121, 121, 121, 121, 121, 121, 121, 121, 122) + List(53, -2, -48, 47, 98, -11, -73, 89, 24, -16, 122, -22, -52, -112, 110, -5, -47, -93, 33, -78, 30, 101, -75, 105, 48, -118, 86, -94, -111, 6, 99, 80, 123, 106, 114, -94, -106, -56, -14, 85, -81, -111, 4, -65, 10, -38, -56, -83, 73, 51, -80, 34, -116, 112, -125, -89, -107, 77, 69, -123, -121, -55, 104, 24, 105, 93, 60, -88, 50, -117, 21, -17, 119, 56, 51, -53, 63, 116, -48, 13, -35, 67, -3, -73, -126, 58, -117, 19, -24, -18, -18, -73, -108, -3, -100, 30, 47, -32, -52, -22, -108, 37, 110, 79, -37, -78, -2, 72, 99, -42, 30, 102, -70, -33, -52, -32, -109, -37, 104, 26, 126, 67, 80, 101, 15, 1, -101, 21, -38, -95, 32, -24, 12, -75, -92, 28, 124, -65, 39, -58, 68, -58, 70, -90, -17, -29, -12, 1, 37, 84, 91, 61, 13, -28, 73, -112, -47, 42, -12, 64, -21, -95, 67, -113, -109, 28, 67, 35, -13, 81, -109, -49, 63, -20, -98, -112, 64, -53, 51, -96, -49, -111, 28, 46, 97, 77, -115, 78, -61, 110, 105, -4, -88, 0, -127, -66, -59, -65, -4, -105, -120, 53, 49, 2, 60, -7, -83, -102, -128, -118, -77, 77, 28, -126, 58, 16, 4, 70, 28, 91, 96, -73, 29, -126, -6, 8, 112, 122, 40, 48, -45, 0, 24, -91, -5, -59, 61, 122, -96)
(468 bytes of data, 239 bytes of metadata)
Unsorted to "One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin. He lay on his armour-like back, and if he lifted his head a little he could see his brown belly, slightly domed and divided by arches into stiff sections. The bedding was hardly able to cover it and seemed ready to slide off any moment. His many legs, pitifully thin compared with the size of the rest of him, waved about helplessly as he looked."

```

It's only 468 bytes, but still an interesting test. The metadata used to unsort it is 239 bytes.

When I tested it against 4096 bytes of random data (not shown), the metadata was 3967 bytes.

# Answer
> 1 votes
## Python 2.x - Score ?

I acrually have no idea how to calculate the score in this case. I use bubble sort and log the swaps along the way. Now, these swaps can then be applied in reversed order to get the original list back. Give the program a `-r` flag when restoring (ie. `file.py -r`)

I have a feeling the most optimal way in the long run is to just save the indexes for each value. But that isn't fun.

```
import sys
import binascii

def sort(data):
    swaps = ''
    swapped = True
    while swapped:
        swapped = False
        for i in xrange(len(data)-1):
            if data[i] > data[i+1]:
                temp = data[i]
                data[i] = data[i+1]
                data[i+1] = temp
                swapped = True
                swaps += '1'
            else:
                swaps += '0'
    swaps = swaps[:-len(data)+1]
    swaps += '0'
    while len(swaps) % 8 != 0:
        swaps += '1'
    swaps = int(swaps, 2)
    swaps = binascii.unhexlify('%x' % swaps)
    return ''.join(map(chr, data)) + swaps + binascii.unhexlify('%08x' % len(swaps))

def unsort(data, swaps):
    swaps = bin(int(binascii.hexlify(swaps), 16))[2:]
    swaps = swaps[::-1]
    while swaps[0] != '0':
        swaps = swaps[1:]
    swaps = swaps[1:]
    datalen = len(data) - 2
    i = datalen
    for s in swaps:
        if s == '1':
            temp = data[i]
            data[i] = data[i+1]
            data[i+1] = temp
        i -= 1
        if i < 0:
            i = datalen
    return ''.join(map(chr, data))

if __name__ == '__main__':
    if len(sys.argv) > 1 and sys.argv[1] == '-r':
        data = sys.stdin.read()
        size = int(binascii.hexlify(data[-4:]), 16)
        swaps = data[-size-4:-4]
        data = map(ord, data[:-size-4])
        print unsort(data, swaps)
    else:
        data = map(ord, sys.stdin.read())
        sys.stdout.write(sort(data))
        sys.stdout.flush()

```

Example:

```
In:  94731
Out: 13479 ÷╚⌂

-r flag
In:  13479 ÷╚⌂
Out: 94731

```

# Answer
> 0 votes
Theoretical solution:

Will work, but chances for it to complete within the time limit are pretty low.

Through brute-force search I try to find any random seed that, when used to shuffle of the original indexes, happens to create exactly the ordered list.

Sample output:

```
Input: [185, 60, 253, 77, 64, 146, 155, 66]
Sorted: [60, 64, 66, 77, 146, 155, 185, 253] 7099

```

Now if I could just figure out how to speed this up a little... ;)

```
public class SortRestore {

  public static void main(String[] args) {
    final Random rnd = new Random(123);
    final int[] input = IntStream.iterate(rnd.nextInt(256), s -> rnd.nextInt(256)).limit(2048).toArray();
    System.out.println("Input: " + Arrays.toString(input));
    final int[] sorted = Arrays.copyOf(input, input.length);
    Arrays.parallelSort(sorted);
    System.out.print("Sorted: " + Arrays.toString(sorted) + " ");
    final List<Integer> indexBase = IntStream.range(0, input.length).boxed().collect(Collectors.toList());

    IntStream.rangeClosed(0, Integer.MAX_VALUE).parallel()
            .filter(seed -> {
              final List<Integer> indexes = new ArrayList<>(indexBase);
              Collections.shuffle(indexes, new Random(seed));
              for (int i = 0; i < input.length; ++i) {
                if (input[i] != sorted[indexes.get(i)]) {
                  return false;
                }
              }
              return true;
            }).limit(1)
            .forEach(System.out::println);
  }
}

```

# Answer
> 0 votes
Performs selection sort and records all the swaps.

Input: \[15, 18, 1, 6, 2, 16, 13\]

Output: \[1, 2, 6, 13, 15, 16, 18\] \[(0, 2), (1, 4), (2, 3), (3, 6), (4, 6)\]

Also: list == restore(\*sort(list))

```
def swap(l, indexes):
    l[indexes[0]], l[indexes[1]] = l[indexes[1]], l[indexes[0]]

def sort(l):
    restore = []
    for i in range(len(l)-1):
        m = min(l[i+1:])
        if l[i] > m:
            restore.append((i,l.index(m)))
            swap(l, restore[-1])

    return l, restore

def restore(l, restore):
    restore.reverse()
    for i in restore:
        swap(l,i)
    return l

```

# Answer
> 0 votes
# J

Not sure how this should be scored, but it's a simple deal with J.

* `/:~` sorts the list.
* `A.@/:@/:` gives the restoration information, an integer less than N! for a list of length N, which can be coded into ceil(*log*256 N!) bytes or less, using `(256#.3&u:)inv`, and decoded with `(256#.3&u:)`.
* `((A.i.@#){])` takes the restoration integer on the left and the sorted array on the right.

The integer is literally a permutation number—that's what the `A.` is doing, converting between permutations and permutation numbers.

If you need a single program that can convert between the two, you're probably looking at something like:

```
(/:~;4 u:256#.inv A.@/:@/:) :(]{~i.@#@]A.~256#.3 u:[)

```

which sorts and gives the restore if it's used with one argument, or takes the restoration on the left and the sorted array on the right to fix it.

For the record, the J equivalent of Python's trivial solution, where the restoration information is the array itself, is the simple `(;~/:~) :[`.

---
Tags: code-challenge
---


title: Are Pigs able to fly?

text:
# Question
Title: Are Pigs able to fly?
# Task

Your task is to write a function or a program in a language of your choice that analyzes a couple of statements and determines whether it can be concluded from those statements that pigs are able to fly.

# Input

The input is a String that can be read from STDIN, taken as a function argument or even be stored in a file. The input can be described using the following EBNF:

```
input = statement , {statement};
statement = (("Pigs are ", attribute) | ("Everything that is ", attribute, "is also ", attribute)), ". ";
attribute = [not], ("able to fly" | singleAttribute);
singleAttribute = letter, {letter};
letter = "a" | "b" | "c" | "d" | "e" | "f" | "g"
       | "h" | "i" | "j" | "k" | "l" | "m" | "n"
       | "o" | "p" | "q" | "r" | "s" | "t" | "u"
       | "v" | "w" | "x" | "y" | "z" ;

```

**Example input (see more examples below):**

```
Pigs are green. Everything that is green is also intelligent. Everything that is able to fly is also not intelligent. Pigs are sweet.

```

# Output

The output can be returned by your function, be written to a file or print to STDOUT. There are 5 different cases to be handled:

1. The given statements are valid, consistent and have as a logical consequence that pigs can fly. In that case, you must output `Yes`.
2. The given statements are valid, consistent and have as a logical consequence that pigs can not fly. In that case, you must output `No`.
3. It can not be concluded from the given, valid and consistent statements whether pigs can fly or not. In that case, you must output `Maybe`.
4. The given statements are valid, but not consistent (i.e. there's a contradiction in the given statements). Since *ex falso quodlibet*, we decide to output `Yes` in that case.
5. The given statements are not valid, i.e. they are not formatted according to the given EBNF. In that case, you may do whatever you want.

# Details

* You may assume that the given attributes are independent from each other. So, for example, a pig may be young and old, green, red and blue at the same time without causing any inconsistency. However, a pig may not be 'green' and 'not green' at the same time, that's a contradiction and should be handled as described in (4).
* For every attribute, assume that there is at least one object (not necessarily a pig) in the universe that has the given attribute, and one object that doesn't have it.

# Example Inputs & Outputs

**Input:**

```
Pigs are green. Everything that is green is also intelligent. Everything that is able to fly is also not intelligent.

```

**Output:** Since Pigs are green and therefore intelligent, and everything that is able to fly is not intelligent, pigs cannot fly. Output is `No`.

**Input:**

```
Pigs are old. Everything that is not able to fly is also not old.

```

**Output:** If pigs were not able to fly, they were also not old. But as they are old, you must output `Yes`.

**Input:**

```
Everything that is sweet is also not old. Everything that is intelligent is also blue.

```

**Output:** `Maybe`.

**Input:**

```
Pigs are not able to fly. Everything that is red is also sweet. Everything that is sweet is also not red.

```

**Output:** Although the first statement implies that pigs can not fly, the following statements contradict each other and therefore the output must be `Yes`.

**Input:**

```
Pigs are very smart. Pigs are able to fly.

```

**Output:** Whatever you want, as the String doesn't match the criteria mentioned above.

# Winner

This is , so the shortest correct answer (in bytes) wins. The winner will be chosen one week after the first correct answer is posted.

# Answer
> 10 votes
# Perl, 363 353 350 347 343 297 266 264

```
$_=<>;s/able to fly/X/g;$m=' ?(not )?\b(P|\w+)';$h{$1?N.$2:$2}{$3?N.$4:$4}=$h{$3?$4:N.$4}{$1?$2:N.$2}=1while s/$m.{8}$m\.//;map{%x=0,r($_,$_)}%h;sub r{($a,$b)=@_;$e+=$h{$a}{N.$b};$x{$b}++or$h{$a}{$b}=1,map{r($a,$_)}%{$h{$b}}}print$e|$h{P}{X}?Yes:$h{P}{NX}?No:Maybe

```

Ungolfed/Explanation:

```
# Read one line from STDIN
$_=<>;
# Replaces special attribute with X
s/able to fly/X/g;
# Prepare attribute match
$m=' ?(not )?\b(P|\w+)';
# Match "Everything that is A is also B. "
#                        "\bA........ \bB\."
# Match "Pigs are B. "
#     "\bP........\bB\."
while(s/$m.{8}$m\.//)
{
  # Add facts for A => B and !B => !A, where A may equal "P" for "Pigs are"
  # Facts are stored as a hash of hashes %h; keys%h are the source attributes;
  # keys%{$h{$a}} are the attributes that follow from attribute $a
  # A "not attribute" is stored as "Nattribute", while a "attribute" is just stored as "attribute"
  $h{$1?N.$2:$2}{$3?N.$4:$4}=$h{$3?$4:N.$4}{$1?$2:N.$2}=1
}
# For all known source attributes ... (this should really be keys%h but we dont mind the extra hashrefs)
map{%x=0,r($_,$_)}%h;
sub r
{
  ($a,$b)=@_;
  # ... remember that we hit a negation and therefor an inconsistency ...
  # If we check/add $b and find an existing "N$b" that means that attribute $b is supposed to be true and not true at the same time
  # It is cheaper bytewise to just add up all consistency errors (remember each fact has a hard value of 1) than to exit right here
  $e+=$h{$a}{N.$b};
  # ... remember that we processed this attribute for the current source attribute so we prevent loops ...
  $x{$b}++or
  # ... add a new fact and then follow the chains (again omitting keys).
  $h{$a}{$b}=1,map{r($a,$_)}%{$h{$b}}
}
# Did we happen on an inconsistency? Do pigs fly? Dont pigs fly? Maybe (Bitwise or is okay too)
print$e|$h{P}{X}?Yes:$h{P}{NX}?No:Maybe

```

# Answer
> 10 votes
# Haskell, 586 566 547 bytes

I wrote this on the assumption that for every property *P* there must exist some *x* and *y* such that *P(x)* is true and *P(y)* is false; without this assumption, the fourth example input wouldn't have a contradiction and would answer "No".

```
#define X p s q m
#define W where
t=0<1;f=0>1;y="Yes"
l=length;r=filter;h=head;(#)=(,)
u 0=[[]];u n=[x:y|x<-[t,f],y<-u$n-1]
c l=all(==h l)l#and l
X[]|or[fst$c$map(!!(n-1))e|n<-[1..l$h e]]=y|z t=y|z f="No"|t="Maybe"W e=m$u$l s;z m=t#m==(c$map h$q e)
X("Pigs":_:y)=p v((r$(==a).(!!k)).q)m z W((k,v),z,a)=s%y
X(_:_:_:y)=p w q((r(\x->(x!!j/=a)||(x!!k==b))).m)v W((j,u),_:_:z,a)=s%y;((k,w),v,b)=u%z
s%("not":w)=(i,u,not p)W(i,u,p)=s%w
s%(_:"to":_:w)=(0#s,w,t)
s%(w:z)=(maybe(l s,s++[w#l s])(#s)$lookup w s,z,t)
main=interact$p[""#0]id id.words.r(/='.')

```

This should be compiled with the ghc command line option "-cpp". Input must be terminated by EOF (^D). You can try it online at http://melpon.org/wandbox/, but you cannot set command line options. Instead, you can prefix the program with the language option

```
{-# LANGUAGE CPP #-}

```

It works by collecting the set of traits, then filtering the set of trait -\> truth valuations using the implications in the input. The result is then tested to ensure that every trait can be validly assigned to both True and False (failure here is the *ex falso quodlibet* case). Finally, it looks for valuations which match the pig facts, checking the value for "able to fly" in each valuation.

Quite a few bytes were lost to threading state around: the set of traits seen so far, the pig-fact-selector function, and the filtering function determined by the implications. Probably the exact same idea would be much shorter in an impure language.

*Edit:* Saved several bytes by proud haskeller's suggestion, then a couple extra by replacing the binding of z and "u%drop 2 z" with a binding to "\_ : _ : z" and "u%z", saving 3.

*Edit 2:* Saved some more. Used the (#)=(,) trick to save 2 bytes and learned about pattern synonyms (https://ghc.haskell.org/trac/ghc/wiki/PatternSynonyms), but the notation was too verbose to get a savings from eliminating the rest of the pairs in this program. Squeezed out some more savings by changing the patterns that the parser searches for. For example: if a sentence doesn't start with Pigs and we have anything left in the parser state, we parse a "Everything that is.." sentence. This saved lots of characters in the patterns for X and %.

# Answer
> 6 votes
# Python, ~~547~~ ~~536~~ ~~525~~ ~~521~~ ~~513~~ ~~509~~ ~~497~~ ~~503~~ 501

```
m=map
o='not ';R={'':{''}}
S=lambda x,y:filter(len,m(str.strip,x.split(y)))
N=lambda a:[o+a,a[4:]][a[:4]==o]
def C(s):a,c=S(s[19:],'is also');return[(a,c),(N(c),N(a))]
X=lambda A:A&set(m(N,A))and 1/0 or A
for a,c in sum(m(lambda x:[('',x[9:])]if'P'==x[0]else C(x),S(raw_input(),'.')),[]):R.setdefault(a,{a}).add(c)
def F(s):
 i,n={s},{s}
 while 1:
  for r in i:n|=R.get(r,n)
  if X(i)>=n:return i
  i|=n
try:a='able to fly';n=N(a);c={n:'No','':'Maybe'}[''.join({a,n}&m(F,R)[0])]
except:c='Yes'
print c

```

For each `a -> b` in the input, we add the given clause and its negation `not b -> not a` to the set of clauses and then compute the set of propositions that are `->`-reachable from any proposition using a fixpoint loop. Whenever we encounter a contradiction, we throw (and later catch) a `ZeroDivisionError` and print `Yes`.

Finally, we check if 'able to fly' (and/or its negation) is reachable from the 'is pig' proposition `''` and print the appropriate response.

**EDIT**: ~~This is buggy, fixing it.~~ Fixed.

# Answer
> 5 votes
## Ruby 1.9.3 (~~365 364~~ 362)

```
h='able to fly'
i="(not )?(#{h}|\\w+)"
o=->s{n=Regexp.new(i+" (is also|are) "+i).match s
[[n[2],!n[1]],[n[5],!n[4]]]}
c=e=!z=[]
w=->r{z.member?(r)||(z<<(a,b=r)
c|=a[0]==b[0]&&a[1]!=b[1]
w[[[b[0],!b[1]],[a[0],!a[1]]]]
z.map{|q|q[1]==r[0]&&w[[q[0],r[1]]]})}
y=->x{z.member?([[p='Pigs',!e],[h,x]])}
f=->x{x.split(?.).map{|s|w[o[s]]}
c|y[!e]?'Yes':y[e]?'No':'Maybe'}

```

### Usage

The code above defines a function `f`, which takes one parameter representing the textual input and returns `Yes`, `No`, or `Maybe`.

For example:

```
f['Pigs are old. Everything that is not able to fly is also not old.']
=> "Yes"

```

### Online test: http://ideone.com/fxLemg

The ungolfed code (including unit tests) is available here.

---
Tags: code-golf, natural-language, logic
---


title: Trap the mouse!

text:
# Question
Title: Trap the mouse!
Write the shortest program possible that traps the mouse cursor inside an upward pointing equilateral triangle with a side length of 274 pixels and a centroid at the exact middle of the screen.
(Triangle because of cheese wedges.)

While your program is running, the tip of the cursor should never be able to move outside of this triangle, and should move and function normally inside. When the `Esc` key is hit the program must end, releasing the mouse.

# Scoring

This is code-golf, the shortest code in bytes wins. You may only use standard ASCII.

# Details

* Besides things like shutting off the computer or killing the process or pressing `Alt-F4` or `Ctrl-Alt-Delete`, the only way to release the cursor should be the `Esc` key.
* If the cursor is outside the triangle when the program starts it should be placed somewhere inside.
* The cursor must be able to move smoothly up and down the two angled sides of the triangles.
* If the display is extended over multiple monitors the triangle may appear in the center of any one monitor or the center of all of them combined. (If you only have one monitor you do not need to test for this.)
* It's fine if touchscreen users can still click things outside the triangle.

*Tiny bonus question:* Where did I get 274 from?

# Answer
# AutoHotKey (249)

```
CoordMode,Mouse
Esc::ExitApp
U(a,b){
return(a+b+abs(a-b))/2
}
L(a,b){
return(a+b-abs(a-b))/2
}
t::
SysGet,X,0
Sysget,Y,1
M:=X/2
N:=Y/2
Loop{
MouseGetPos,x,y
MouseMove L(U(M-137,x),M+137),L(U(N-118+1.732*abs(x-M),y),N+119),0
}
return

```

It doesn't have inbuilt min/max functions, so I spent 72 chars reimplementing them.

Press `t` to trap the cursor, I dont know if its possible to do stuff without assigning it to a hotkey.

The movement is not very smooth, unless you move the mouse slowly
> 0 votes

# Answer
## Python ~~418~~ ~~351~~ ~~314~~ ~~300~~ 263 Bytes

Edit: Saved ~~67~~ ~~104~~ ~~118~~ 155 Bytes thanks to the advice in the comments

```
from win32api import*
from msvcrt import*
s=137
G=GetSystemMetrics
S=SetCursorPos
x=G(0)//2
y=G(1)//2
c=3**.5
Y=y-2*s/c
S((x,y))
while(kbhit()and ord(getch())==27)<1:a,b=GetCursorPos();S((min(max(a,x-s),x+s),min(max(b,int(c*a+Y-c*x),int(-c*a+Y+c*x)),int(y+s/c))))

```

Written in Python 3.4.1 on Windows, pywin needs to be installed.

My first code golf submission. Please feel free to suggest improvements
> 2 votes

---
Tags: code-golf
---


# Question
Title: Find 10 large prime numbers with n digits
You are given *n* (200 ≤ *n* \< 250) as a command line argument. Print 10 prime numbers with *n* digits. Your program should run under 1s and must be shorter than 5000 bytes (excluding).

Sum the digits of all your 500 primes. Program with the largest sum wins.

An example (more here):

```
$ ./find_large_primes 200
58021664585639791181184025950440248398226136069516938232493687505822471836536824298822733710342250697739996825938232641940670857624514103125986134050997697160127301547995788468137887651823707102007839
29072553456409183479268752003825253455672839222789445223234915115682921921621182714164684048719891059149763352939888629001652768286998932224000980861127751097886364432307005283784155195197202827350411
41184172451867371867686906412307989908388177848827102865167949679167771021417488428983978626721272105583120243720400358313998904049755363682307706550788498535402989510396285940007396534556364659633739
54661163828798316406139641599131347203445399912295442826728168170210404446004717881354193865401223990331513412680314853190460368937597393179445867548835085746203514200061810259071519181681661892618329
71611195866368241734230315014260885890178941731009368469658803702463720956633120935294831101757574996161931982864195542669330457046568876289241536680683601749507786059442920003278263334056542642264651
28591045597720075832628274729885724490653298360003309382769144463123258670807750560985604954275365591715208615509779345682419533206637382048824349415329839450792353652240682445321955199147316594996133
49790921912819110019003521637763748399072771256062128988437189616228355821145834783451215869998723492323628198577054239101181556609916127864608488018093426129641387774385490891035446702272744866010729
15474811206486587193258690501682404626361341756658894201908294153626080782693777003022566996735796983239343580281979005677758015801189957392350213806122307985157041153484138150252828152419133170303749
12654646219963267405298825104551142450213038420566798208417393291567314379831789259173233506811083774527183953999862675239292185131178671317061020444490733287588383918793095608410078925861028249824377
40992408416096028179761232532587525402909285099086220133403920525409552083528606215439915948260875718893797824735118621138192569490840098061133066650255608065609253901288801302035441884878187944219033

```

You can use this program to test for primality.

**EDIT**:

Use the following program to compute your score:

```
#!/usr/bin/python
# Usage: ./v.py ./find_large_primes

import subprocess
import sys

sum_ = 0
for n in xrange(200, 250):
  p = subprocess.Popen(
                   args=[sys.argv[1], str(n)],
                   stdout=subprocess.PIPE)
  p.wait()

  sum_ += sum(int(e) for e in p.stdout.read() if e.isdigit())
  p.stdout.close()

print sum_

```

# Answer
## C++ with GMP

```
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

int main(int argc, char *argv[]) {
  int d = atoi(argv[1]);
  int i = 0;
  mpz_t n;
  mpz_init(n);
  mpz_ui_pow_ui(n, 10, d);
  mpz_sub_ui(n, n, 1);
  while (i < 10) {
    if (mpz_probab_prime_p(n, 100)) {
      printf("%s\n", mpz_get_str(NULL, 10, n));
      i += 1;
    }
    mpz_sub_ui(n, n, 2);
  }
}

```

It runs in just under a second on my machine. I'm too lazy to run it 50 times and sum up the digits, but it should be pretty good, as most of the digits (all but the last 4 of each number) are 9s.

```
> ./a.out 250
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999967
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999323
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999017
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998731
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997471
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999996959
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995077
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999993529
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999993511
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999992459

```
> 3 votes

# Answer
# Perl

```
use Math::Prime::Util ":all";
my $n = "1"."0"x shift;
print $n=prev_prime($n),"\n" for 1..10;

```

score 1002616, On 4770K, takes about 0.1s for an argument between 200 and 250; under 4 seconds for the score program. Time for a given run stays under 1s until 455 digits. Note that the Math::Prime::Util and Math::Prime::Util::GMP modules should be installed.

`prev_prime` uses ES BPSW as the primality test, so a little more stringent than Pari's `precprime`.
> 1 votes

---
Tags: code-challenge, primes, restricted-time
---


title: Calculate the Riemann Zeta Function

text:
# Question
Title: Calculate the Riemann Zeta Function
Calculate the Riemann zeta function to the maximum primitive precision in your language (for C-family, that would be `double` or `long double`, `var` in JS, etc.) No need for `BigDecimal` or the like unless you need it to use a `double`-equivalent precision.

1. Efficiency (be sane) doesn't matter.
2. If it's not in a common language, I can't test it, but I hope somebody does.
3. **No libraries or built-in math functions.**
4. Recursion is cool!

See my JS entry for a sample program.

# Answer
# JavaScript (Chrome): 78

```
function zeta(r){for(var t=0,a=1,n=1;t!=a;a=t,t+=1/Math.pow(n++,r));return t}

```
> -1 votes

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


# Question
Title: Compress and Decompress sentence using vowel based encryption cipher
The aim is to parse a sentence and `compress/encrypt` it according to the rules below and then `decrypt` it using the `key`:

1. Remove all letters in a word before the first vowel is encountered. Example: `pigeon` becomes `igeon`.
2. All characters except alphabets should be kept in the sentence including numerals, punctuations, etc. Example: `200-storey building` becomes `200-orey uilding`.
3. Generate the shortest key array `char[] = {a,b,x,<your data>}` and write code to generate the original sentence using this key.

You need to write two functions: `encrypt()` and `decrypt()` which works for every sentence minimising the key-size.

Example 1:

> **Input:** The most technologically efficient machine man has ever invented is the book. -Northrop Frye-
>
> **Output:** e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
>
> **Example key:** {T,m,t,m,h,b,N,F,14,2,5}

Example 2:

> **Input:** "I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day
>
> **Output:** "I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: udgment ay
>
> **Example key:** {n,y,c,2,b,2,m,T,J,D,15}

**Winning Criteria:**

1. Write function `encrypt()` with input from `stdin` or `file` which generates `output` sentence and a `key` on `stdout` or `file` or `memory`.
2. Write function `decrypt()` with inputs the generated sentence and `key` from `encrypt()` and produces the original sentence.
3. This is `code-golf` so cumulative size of the two functions should be minimum. In case of tie-breaker, the generated key-size should be minimum.

# Answer
# Perl5 61 + 30 = 91 ~~122~~ ~~211~~

This is based on the same idea as Comperendinous' Haskell answer where the key is indeed the whole cleartext and I cannot see anywhere in the rules that prevent this so kudos to Comperendinous :)

```
sub encrypt{$k=$_=<>;s/(.*?)\b[^\W\daeiou]+/$1/gi;print$_.$k}
sub decrypt{$i=<>;$_=<>;print}

```

**Perl5 - 91 + 31 = 122**

Here the key is slightly larger, but it actually prrduces the cleartext from the chipertext with the key so I find this more kosher.

```
sub encrypt{$_=<>;$k="s/(.{$+[1]})/\$1$+/;$k"while s/(.*)\b([^\d\Waeiou]+)/$1/i;print$_.$k}
sub decrypt{$_=<>;eval<>;print}

```

Ungolfed (though I've changed it to take parameters instead of two lines of text):

```
sub encrypt {
  my ($str) = @_;
  my $key = '';
  while( $str =~ s/(.*)\b([^\d\Waeiou]+)/$1/i ){
    $key = "\$str=~s/(.{$+[1]})/\$1$2/;$key";
  }
  ($str, $key);
}

sub decrypt {
  my ($str, $key) = @_;
  eval $key;
  $str;
}

```

**Perl5 - 114 + 75 + 22 (shared) = 211**

```
sub encrypt{$_=<>;@k=m/\b$x/ig;push@_,$+[1] while s/(.*?)\b$x/$1/i;print$_.join'',(@_,@k)[map{$_,$_+@k}0..$#k],$/}
sub decrypt{$i=<>;$_=<>;%k=m/(\d+)$x/g;print map{$k{$%++}|(),$_}split//,$i}
$x='([^\d\W\daeiou]+)'

```

With both functions chipertext is always output/input first, then the key.

Examples:

```
Input:
The most technologically efficient machine man has ever invented is the book. -Northrop Frye-

Output:
e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
0Th2m6t31m38m41h61th63b69N77Fry

Input:
"I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day

Output:
"I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: udgment ay
3n7y11cl18y22b31y35m50Th52T60T73J81D

```

Ungolfed code:

```
# credit: http://stackoverflow.com/a/71895/1565698
sub zip {
    my $pivot = @_ / 2;
    return @_[ map { $_, $_ + $pivot } 0 .. $pivot-1 ];
}

my $consonants = '([^\d\W\daeiou]+)';

sub encrypt {
  my $str = <>;
  my @matches = $str =~ m/\b$consonants/ig;
  my @indexes = ();
  while( $str =~ s/(.*?)\b$consonants/$1/i ) {
    push @indexes, $+[1]; # @+ has the match positions starting at 1
  }
  my $key = join('', zip(@indexes, @matches));
  print "$str$key\n";
}

sub decrypt {
 my $str =<>;
 my $key =<>;
 my %map = ( $key =~ m/(\d+)$consonants/g );
 my $index = 0;
 my @result = map{ $map{$index++} || (), $_ } split //, $str;
 print join '', @result;
}

```
> 1 votes

# Answer
# Perl (126+67=193 characters)

Key contains each character removed along with its offset.

Encrypt reads one line from STDIN

Decrypt reads two: first the ciphered string then the key

```
sub encrypt{$_=<>;s(.)(++$j,$q|=$&=~/[aeiou]/i,$q^=$&eq$",!$q&$&=~/[a-z]/i&&(push@d,($&,$j-1))||print$&)ge;print$/.join',',@d}
sub decrypt{$q=<>,$_=<>;s/(.),(\d+)/substr($q,$2,0)=$1/gie;print$q}

```

Examples:

```
(encrypting)
The most technologically efficient machine man has ever invented is the book. -Northrop Frye-
> e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
> T,0,h,1,m,4,t,9,m,35,m,43,h,47,t,68,h,69,b,72,N,79,F,88,r,89,y,90

"I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day
> "I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: Judgment ay
> n,3,y,8,c,13,l,14,y,22,b,27,y,37,m,42,T,58,h,59,T,62,T,71,D,94

(decrypting)
e ost echnologically efficient achine an as ever invented is e ook. -orthrop e-
T,0,h,1,m,4,t,9,m,35,m,43,h,47,t,68,h,69,b,72,N,79,F,88,r,89,y,90
> The most technologically efficient machine man has ever invented is the book. -Northrop Frye-

"I eed our othes, our oots and our otorcycle. " - e -800 in erminator 2: Judgment ay
n,3,y,8,c,13,l,14,y,22,b,27,y,37,m,42,T,58,h,59,T,62,T,71,D,94
> "I need your clothes, your boots and your motorcycle. " - The T-800 in Terminator 2: Judgment Day

```

Ungolfed with comments

```
sub encrypt{
    # get input
    $_=<>;
    # for each character
    s(.)(
        # increment j
        ++$j,
        # set q to 1 if vowel
        $q |= $&=~/[aeiou]/i,
        # set q to 0 if space
        $q ^= $& eq $",
        # if q==0 and is a letter (consonant, because q=1 if vowel)
        !$q & $&=~/[a-z]/i &&
            # push both the letter and the offset to @d
            (push @d,($&,$j-1))
        # otherwise print
        || print$&
    )ge;
    # print a newline, then @d
    print$/.join',',@d
}
sub decrypt{
    # read a line to $q, and another to $_
    $q=<>,$_=<>;
    # for each [character],[number] in key
    s/(.),(\d+)/
        # add character back into string
        substr($q,$2,0)=$1
    /gie;
    # print deciphered string
    print$q
}

```
> 1 votes

# Answer
## Haskell: 119 = 111 + 8

Since there's no restriction on the key, I'm going agile and not getting any more complex until someone has a shorter answer:

```
e t=(unwords.map((\(a,b)->filter(not.(`elem`['a'..'z']++['A'..'Z']))a++b).break(`elem`"aeiouAEIOU")).words$t,t)
d(c,k)=k

```

I can make this at least 6 characters shorter if I import isAlpha from Data.Char. It's part of the standard distribution, so is it allowed?
> 1 votes

---
Tags: code-golf, cryptography
---


title: Create shortest log organizer

text:
# Question
Title: Create shortest log organizer
Create the shortest script that organizes all the logs by month and date.

# Rules

**Syntax**

```
organize <folder to scan> <folder to place logs>

```
* folder cannot be root
* the two folder should be different and not contain one another

**Behaviour**

The script should scan all the \*.log files in `<folder to scan>` and copy them to `<folder to place logs>` in sub-folders corresponding to the year and month of the last modified time of the log file, named like `year_month`.

Example:

```
organize /var/log/apache2 /temp/logs

```

would give folder structure like this:

```
/temp/logs/
|-- 2014_01
|-- 2014_02
|-- 2014_03
|-- 2014_04
|-- 2014_05

```

**Languages, environment**

All languages and OSs are permitted but need to be specified.

But since this is a question, script languages (python, bash, windows batch) will be more fit from the start.

# Answer
> 4 votes
## Bash - 79 bytes

```
stat -c" $2/-%n-%y" $1/*.log|awk -F- '{d=$1$3"_"$4;system("mkdir"d";cp "$2d)}'

```

# Answer
> 3 votes
## Batch - 104 bytes

```
@cmd/von/c"for /r %1 %%a in (*.log)do @set a=%%~ta&set a=!a:~6,4!_!a:~3,2!&mkdir %2\!a!&copy %%a %2\!a!"

```

# Answer
> 2 votes
## Bourne Shell / FreeBSD 9.2+ - 92(83) bytes

```
#!/bin/sh
ls -lD"%Y_%m" $1/*.log|cut -wf6-|while read A B;do mkdir $2/$A;cp $1/$B $2/$A;done

```

# Answer
> 2 votes
# Cobra - 223

**OS: Any with Mono/.NET**

Because this is the perfect task for an obscure compiled language! \< /sarcasm\>

```
class P
    def main
        a,b=CobraCore.commandLineArgs[1:]
        for f in Directory.getFiles(a,'*.log')
            m=b+File.getLastWriteTime(f).toString('yyy_MM')
            Directory.createDirectory(m)
            File.copy(f,m+f[f.lastIndexOf('/'):],true)

```

# Answer
> 2 votes
## Powershell (124 bytes)

```
Get-ChildItem $($s+"\*.log")|%{$n=$d+"\"+$_.LastWriteTime.ToString("yyyy_MM");if(!(Test-Path $n)){md $n}mi $($s+$_.Name) $n}

```

Has the added bonus of scanning for only .log files in the given folder if there are multiple file types. If not, then I can knock this down to 112. $s is the full source folder path, and $d is the destination folder path.

---
Tags: code-golf
---


title: Golf a Venn Diagram generator

text:
# Question
Title: Golf a Venn Diagram generator
## Golf a Venn Diagram generator

In order to properly celebrate John Venn's 180th birthday, today your task will be creating a program that outputs a Venn Diagram!

**Input:**

A positive integer `N` that will define the range of numbers appearing in the diagram (From zero to `N`) and three sets of positive integers.

**Output:**

A 3 set Venn diagram showing all integers from 0 to `N` and the relationships of the sets by displaying them in the proper regions of the diagram, similar to this one.

**Notes**

1. Use `stdin` (or whatever your language's equivalent is) to get the values.
2. You can define the input format for the sets and for `N` (Separated by comma, slash or whatever works best for you).
3. Numbers that do not appear in any of the sets but are within the specified range must appear on the diagram, just not inside any region.
4. The sets don't need to be named.
5. The output can be a drawing or ascii-art.
6. The diagram can have any shape as long as the boundaries are unambiguously distinguishable (if you chose ASCII art, using + (or similar) for crossing boundaries is essential, for example).
7. The regions may but don't have to be shaded.
8. Any built-in functions or third party libraries that generate Venn Diagrams are disallowed.
9. Standard loopholes apply.

This is , so the shortest code, in bytes, wins.

# Answer
# Mathematica ~~343~~ 264

## UnGolfed

```
m=Input[]; data=Input[];

(* The circles to represent set boundaries *)
{R1,R2,R3}=Circle[#,5]&/@{{-2,8.5},{2,8.5},{0,5}};

(*converts  {1,0,1} to base 10, ie, the number 5.
bool[x_]:=FromDigits[Boole[x],2]

(* determines the region in which each number from 0 to `m` resides *)
encode[num_]:=bool[Table[MemberQ[data[[k]],num],{k,3}]]

(*Centroid of each region; the first is a location for numbers in none of the three sets *)
points={{7,4},{0,2},{4,10},{3,6},{-4,10},{-3,6},{0,11},{0,7}}

(* Plots the venn diagram with numbers in regions *)
Graphics[{
Text@@@({#[[1]],points[[#[[2]]+1]]}&/@({#[[All,1]],#[[1,2]]}&/@GatherBy[{#,encode[#]}&/@Range[0,m],Last])),
Opacity[.1],R1,R2,R3
}]

```

---

Assuming `10` was input for `m` and `{{1,2,3,4,5,9},{1,2,3,6,8},{7,2,9}}` was input for `d`,

---

## Golfed 264

I was surprised that all of the computation could be carried out within the `Graphics` function itself. With the exception of the inputs, it is a one-liner.

```
m=Input[];d=Input[]
Graphics@{Text@@@({#[[1]],{{7,4},{0,2},{4,10},{3,6},{-4,10},{-3,6},{0,11},{0,7}}[[#[[2]]+1]]}&/@({#[[All,1]],#[[1,2]]}&/@GatherBy[{#,FromDigits[Boole[Table[d[[k]]~MemberQ~#,{k,3}]],2]}&/@Range[0,m],Last])),Circle[#,5]&/@{{-2,8.5},{2,8.5},{0,5}}}

```
> 8 votes

# Answer
## Ruby, ~~654~~ ~~590~~ ~~566~~ ~~542~~ 505 bytes

This was fun. I used ASCII. I wasn't able to test every possible combination yet, so if you find a glitchy test case, please let me know.

```
require'set'
u=(0..gets.to_i).to_set
a,b,c=eval(gets).map &:to_set
i=' '
m,M,n,N,o,O,p,P,q,Q,r,R,s,S=[a-b-c,b-a-c,c-a-b,a&b-c,b&c-a,a&c-b,a&b&c].map{|u|[t=u.to_a*i,t.size]}.flatten
H,V,X=?─,?│,?┼
puts'┌'+H*(A=[1+M+[P,S].max,1+R].max)+?┐+(u-a-b-c).to_a*i,V+i*M+?┌+(b=H*(T=-M+U=A-1)+X+H*(B=[N,Q].max))+?┐,V+m+V+p+i*(T-P)+V+n+i*(B-N)+V,'│┌'+H*(K=M-1)+X+b+X+H*(C=[O-B-1,0].max)+?┐,(v=V*2+i*K)+V+s+i*(T-S)+V+q+i*(B-Q)+V+i*C+V,v+?└+b+?┘+i*C+V,V*2+r+i*(U-R)+V+o+i*(-O+D=B+C+1)+V,'└┼'+H*U+?┘+i*D+V,' └'+H*(A+D)+?┘

```

It expects the input on STDIN in the following format

```
10
[[1,2,3,4,5,9],[1,2,3,6,8],[7,2,9]]

```

And will then reward you with this beauty

```
┌───────┐0 10
│   ┌───┼───┐
│4 5│1 3│6 8│
│┌──┼───┼───┼┐
││  │2  │   ││
││  └───┼───┘│
││9     │7   │
└┼──────┘    │
 └───────────┘

```

I don't think I can be bothered to add an ungolfed version. Please have a look at the original version in the edit history for a *somewhat* more readable version.

This could certainly be golfed further by making the set boundaries less tight or even keeping them fixed like some of the graphical ones do, but I prefer that it looks nice and is done "properly" despite being golfed.
> 45 votes

# Answer
# BBC BASIC, 243 ASCII characters (tokenised file size 211 bytes)

Download emulator at http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

**Golfed**

```
  INPUT"N",n
  DIMs(n+1)
  FORi=0TO2PRINT"S";i
  REPEATINPUTx:s(x)=s(x)+2^i:UNTILx>n
  NEXTMODE4r=360CIRCLE460,r,r
  CIRCLE640,664,r
  CIRCLE820,r,r
  FORi=0TO7FORx=0TOn:IFs(x)=i PRINT;x
  NEXTREADa
  VDU28,a+1792;a+5;
  NEXT
  DATA19,4873,2572,4893,2586,5907,3091,34

```

BBC Basic is very arbitrary about which newlines/whitespace you can eliminate. Apart from stripping out unnecessary newlines there's another trick here that's not in the ungolfed version: I assign the viewport (see explanation below in ungolfed comments) at the END of the plotting loop, not at the beginning. This means that the elements outside the set are plotted the top left, and the cursor is trapped in a viewport at top right at the end of the program. The reason for this is to eliminate the `VDU26`.

**Ungolfed**

Each set of numbers is terminated by the user entering the number N+1 (a slightly unusual choice, this is to avoid errors caused by trying to write outside the range of an array.) Then it changes from a text mode to a graphics mode and plots the Venn diagram.

The input data is stored in an array, one cell for each value to be displayed. The data is stored as a 3-bit value: 1 for Set0 + 2 for Set1 + 4 for Set2 giving a number in the range 0 to 7. BBC basic has no shift operator, so the power operator is used instead: `2^i` instead of `1<<i` in C for example.

After plotting the circles, an outer loops goes through each of the eight regions, moving to the required coordinates (as per a data table.) An inner loop prints all the numbers in that region (those with the corresponding 3-bit value in the array.)

```
  INPUT"N",n                                 :REM create an array called s() with range 0..n+1
  DIMs(n+1)
  FORi=0TO2
    PRINT"S";i                               :REM prompt the user for data for set 0, set 1 and set 2.
    REPEATINPUTx:s(x)=s(x)+2^i:UNTILx>n      :REM input numbers and store as a bit table. Repeat until user enters n+1.
  NEXT
  MODE4                                      :REM change to graphics mode.
  r=360
  CIRCLE460,r,r                              :REM plot a circle at x,y,r.
  CIRCLE640,664,r                            :REM for the bottom two circles y=r.
  CIRCLE820,r,r
  FORi=0TO7                                  :REM for each region of the venn diagram
    READa                                    :REM read a 2 byte value for the  coordinates of the top left corner of a text viewport from the DATA statement: x+256y
    VDU28,a+1792;a+5;                        :REM create a 5x7 viewport (limits each region to 7 numbers.) 1792=7*256
    FORx=0TOn:IFs(x)=i PRINT;x               :REM print all numbers in the array belonging to that region
    NEXT
  NEXT
  VDU26                                      :REM Restore the viewport to the whole screen, to ensure the command prompt does not mess up the display at the end of the program.
  DATA34,19,4873,2572,4893,2586,5907,3091

```

**Montage of typical input and output (ungolfed version)**

In the golfed version, the position of the numbers outside the sets is exchanged with the command prompt `>`.
> 15 votes

# Answer
# Javascript 1235

http://jsfiddle.net/44a4L/7/

Tested in google chrome v36.

Input is taken in the variables upper, set1, set2 and set3.

**Update:** Now automatically scales depending on the size of input.

```
function t(e,t){z.getElementById(e).innerHTML+=" "+t}z=document;s=200+upper*20;z.body.innerHTML+="<style>#m{width:"+s+"px;height:"+s+"px;}div{position:absolute;text-align:center;border-radius:50%;}#s1{left:calc(15% + 15px);top:30px;bottom:30%;right:calc(15% + 15px);background-color:rgba(255,0,0,0.4);padding:10%;}#s2{left:30px;bottom:30px;top:30%;right:30%;background-color:rgba(0,255,0,0.4);padding-right:40%;padding-top:30%;}#s3{right:30px;bottom:30px;top:30%;left:30%;background-color:rgba(0,0,255,0.4);padding-left:40%;padding-top:30%;}#s123{left:40%;top:40%;right:40%;bottom:40%;}#s12{left:20%;top:35%;right:65%;bottom:50%;}#s13{right:20%;top:35%;left:65%;bottom:50%;}#s23{left:40%;right:40%;bottom:15%;top:70%;}</style><div id=m><div id=s1 class=s></div><div id=s2 class=s></div><div id=s3 class=s></div><div id=s123 class=v></div><div id=s12 class=v></div><div id=s13 class=v></div><div id=s23 class=v></div></div>";for(i=0;i<=upper;i++){i1=i2=i3=false;if(set1.indexOf(i)!=-1)i1=true;if(set2.indexOf(i)!=-1)i2=true;if(set3.indexOf(i)!=-1)i3=true;if(i1&&i2&&i3)t("s123",i);else if(i1&&i2)t("s12",i);else if(i1&&i3)t("s13",i);else if(i2&&i3)t("s23",i);else if(i1)t("s1",i);else if(i2)t("s2",i);else if(i3)t("s3",i);else t("m",i)}

```

Sample output:
> 14 votes

# Answer
# HTML + JavaScript (E6) 752 ~~761~~

Input format: *max set1 set2 set3* (each set is a comma separated list of numbers)

Example: 10 1,2,3,4,5,9 1,2,3,6,8 7,2,9

Example 2: 30 2,4,6,8,10,12,14,16,18,30 3,6,9,12,15,18,21,30 5,10,15,20,25,30

All the sections auto size thanks to html rendering.

```
<html><body><script>
i=prompt().split(' ');
r=",,,,,,,, class=',></i>".split(c=',')
for (j=-1;j++<i[0];r[h]+=j+' ')for(h=k=0;++k<4;)if((c+i[k]+c).search(c+j+c)+1)h+=k+(k>2);
document.write(
"<style>div{1row}p{position:relative;text-align:center;padding:7;1cell}i{position:absolute;top:0;3:0;4:0;left:0}.a{2top-left5b{2top-45c{23-left5d{23-45x{6880,9.y{680,89.z{60,889</style>"
.replace(/\d/g,x=>'09display:table-9border-9bottom9right9-radius:60px}.9background:rgba(930px9255,9.3)}'.split(9)[x])
+"<div><p8x a'/><p8x'>1</p><p><i8y a'9<i8x b'93</p><p8y'>2</p><p8y b'/></div><div><p8x c'/><p8z a'><i8x'95</p><p8z'><i8x d'9<i8y c'97</p><p8z b'><i8y'96</p><p8y d'/></div><div><p/><p8z c'/><p8z'>4</p><p8z d'/></div>0"
.replace(/\d/g,x=>r[x]))
</script></body></html>

```

**Javascript E5 version** Works in Chrome and MSIE 10 (maybe 9)

```
<html><body><script>
i=prompt().split(' ');
r=",,,,,,,, class=',></i>".split(c=',')
for (j=-1;j++<i[0];r[h]+=j+' ')for(h=k=0;++k<4;)if((c+i[k]+c).search(c+j+c)+1)h+=k+(k>2);
document.write(
"<style>div{1row}p{position:relative;text-align:center;padding:7;1cell}i{position:absolute;top:0;3:0;4:0;left:0}.a{2top-left5b{2top-45c{23-left5d{23-45x{6880,9.y{680,89.z{60,889</style>"
.replace(/\d/g,function(x){return '09display:table-9border-9bottom9right9-radius:60px}.9background:rgba(930px9255,9.3)}'.split(9)[x]})
+"<div><p8x a'/><p8x'>1</p><p><i8y a'9<i8x b'93</p><p8y'>2</p><p8y b'/></div><div><p8x c'/><p8z a'><i8x'95</p><p8z'><i8x d'9<i8y c'97</p><p8z b'><i8y'96</p><p8y d'/></div><div><p/><p8z c'/><p8z'>4</p><p8z d'/></div>0"
.replace(/\d/g,function(x){return r[x]}))
</script></body></html>

```

**Not (so) golfed**

```
<html>
<style>
div {   display:table-row; }
p {
    position: relative;
    text-align: center;
    padding: 30px;
    display: table-cell;
}
i {
    position: absolute;
    top:0;bottom:0;right:0;left:0;
}
.a { border-top-left-radius: 60px; }
.b { border-top-right-radius: 60px; }
.c { border-bottom-left-radius: 60px; }
.d { border-bottom-right-radius: 60px; }
.x { background: rgba(255,255,0,.3) }
.y { background: rgba(255,0,255,.3) }
.z { background: rgba(0,255,255,.3) }
</style>
<body>
<div>
<p class='x a'/><p class='x'><b id='b1'></b></p><p><i class='y a'></i><i class='x b'></i><b id='b3'></b></p><p class='y'><b id='b2'></b></p><p class='y b'/>
</div>
<div>
<p class='x c'/><p class='z a'><i class='x'></i><b id='b5'></b></p><p class='z'><i class='x d'></i><i class='y c'></i><b id='b7'></b></p><p class='z b'><i class='y'></i><b id='b6'></b></p><p class='y d'/>
</div>
<div>
<p/><p class='z c'/><p class='z'><b id='b4'></b></p><p class='z d'/>
</div>
<b id='b0'></b>
<script>
i=prompt().split(' ')
r=',,,,,,,'.split(c=',')
for (j=-1; j++<i[0];)
{
    for(h = k = 0; ++k < 4;)
    {
    if( (c+i[k]+c).search(c+j+c) >= 0)
      h += k + (k>2); // bit mask 1 or 2 or 4
  }
  r[h] += j + ' ';
}
for (j = 0; j < 8; j++)
    document.getElementById('b'+j).innerHTML=r[j]
</script>
</html>

```
> 5 votes

# Answer
# Python - 603

```
import re
n,a,b,c=eval(input())
h=set(range(n+1))-a-b-c
g=a&b&c
d,e,f=a&b-g,b&c-g,a&c-g
l,m=set(a),set(b)
a-=b|c
b-=l|c
c-=l|m
for t in'abcdefgh':exec("%s=' '.join(map(str,%s))"%(2*(t,)))
l=len
x,y,z=max(l(a),l(f)+2,3),l(max(d,g)),max(l(b),l(e)+2,l(c)-l(f+g)-2,3)
j=[0]*4
for t in'abcdefg':exec("%s=%s.ljust([x,z,x+y+z-2,y,z-2,x-2,y][ord('%s')-97])+'|'"%(3*(t,)))
s='\d| '
w=re.sub
for r in (1,3):q=r//2;j[r]=['','| '][q]+'|'+[a+d+b,f+g+e][q]+['',' |'][q];j[r-1]=w('\|','+',w(s,'-',j[r]))
j[0]+=h
o=j[2]
j[2]='| +'+j[2][3:-3]+'+ |'
p='  |'+c
q='  '+w('\|','+',w(s,'-',p))[2:]
for l in j+[o,p,q]:print(l)

```

Input is N followed by the three sets, seperated by commas (e.g. `8, {1,2,4}, {2,3,4,5}, {4,6,8}`). It outputs a set in ACSII art like the following:

```
+---+-+---+0 7
|1  | |3 5|
| +-+-+-+ |
| |2|4| | |
+-+-+-+-+-+
  |6 8  |
  +-----+

```
> 4 votes

# Answer
# perl 388b 346b 488b

This has output similar to another entry:

```
@a=split($",<>);
$n=pop @a;
@a=map[split(',')],@a;
for$i(0..2){$b{$_}+=1<<$i foreach@{$a[$i]}}
push@{$c[$b{$_}]},$_ for(0..$n);
$l|=length($d[$_]=join($",@{$c[$_]}))for(0..$n);
print$h=(("+-"."-"x$l)x3)."+
";
sub j{sprintf"% ".(sprintf"%ds",$l+($_[0]<4)+($_[0]==7)),$d[$_[0]]}
sub r{join('|',map{j($_)}@_)}
$h=~s/\+-/|+/;
$h=~s/-\+$/+|/;
print "|".r(1,3,2)."|
".$h;
$h=~s/[|+]{2}/++/g;
print "||".r(5,7,6)."||
".$h;
$h=~s/\+\+/ +/;
$h=~s/\+\+/+ /;
$h=~s/-\+-/---/g;
$l=$l*3+3;print " |".j(4)."|
",$h,$d[0]

```

Test run and output:

```
# echo "1,2,3,7,13 2,3,8,11,13,6,9 3,4,5,11,12,13,14 15" | perl venn.pl ;echo
+----------------+----------------+----------------+
|             1 7|               2|           6 8 9|
|+---------------+----------------+---------------+|
||               |            3 13|             11||
++---------------+----------------+---------------++
 |                                       4 5 12 14|
 +------------------------------------------------+

```
> 3 votes

# Answer
# Python 3 - 353

```
# 353 bytes, input format like: 6 1,2,3 2,3,4 1,3,4
import sys
from turtle import*
_,n,*q=sys.argv
n=set(range(int(n)))
a,b,c=map(set,map(eval,q))
for x,y in(0,0),(-115,-185),(115,-185):goto(x,y),pd(),circle(200),up()
for x,y,s in(200,331,n-a-b-c),(-101,278,a-b-c),(-254,-49,b-a-c),(95,-49,c-a-b),(-172,164,a&b-c),(58,164,a&c-b),(-49,-39,b&c-a),(-49,52,a&b&c):goto(x,y),write(s or'',font=None)
ht()
done()

```

Did anybody else play with Logo as a kid?

Sample: `python3 turtletest.py 15 1,2,3,4,5,9,10,12 1,3,4,6,7,9 1,2,7,8,9`
> 3 votes

# Answer
## T-SQL 2095

Assumes @N is an int containing N. Assumes @A, @B, and @C are tables containing the three sets of numbers. Didn't try to golf it too much.

```
DECLARE @D INT=@N,@E INT=0,@F CHAR='/',@G CHAR='\',@H CHAR='-',@I CHAR='|',@J CHAR='+'DECLARE @ TABLE(Z INT,Y INT,X INT,W INT,V INT,U INT,T INT,S INT)INSERT INTO @(Z)SELECT A.P FROM @A A JOIN @B B ON A.P=B.P JOIN @C C ON A.P=C.P INSERT INTO @(Y)SELECT A.P FROM @A A JOIN @B B ON A.P=B.P LEFT JOIN @C C ON A.P=C.P WHERE C.P IS NULL INSERT INTO @(X)SELECT C.P FROM @C C JOIN @A A ON C.P=A.P LEFT JOIN @B B ON C.P=B.P WHERE B.P IS NULL INSERT INTO @(W)SELECT B.P FROM @B B JOIN @C C ON B.P=C.P LEFT JOIN @A A ON B.P=A.P WHERE A.P IS NULL INSERT INTO @(V)SELECT A.P FROM @A A LEFT JOIN @B B ON A.P=B.P LEFT JOIN @C C ON A.P=C.P WHERE C.P IS NULL AND B.P IS NULL INSERT INTO @(U)SELECT C.P FROM @C C LEFT JOIN @A A ON C.P=A.P LEFT JOIN @B B ON C.P=B.P WHERE B.P IS NULL AND A.P IS NULL INSERT INTO @(T)SELECT B.P FROM @B B LEFT JOIN @C C ON B.P=C.P LEFT JOIN @A A ON B.P=A.P WHERE A.P IS NULL AND C.P IS NULL WHILE @N>=0BEGIN INSERT INTO @(S)SELECT @N WHERE @N NOT IN(SELECT*FROM @A UNION SELECT*FROM @B UNION SELECT*FROM @C)SET @N-=1 END DECLARE @Z TABLE(A CHAR(5),B CHAR(5),C CHAR(5),D CHAR(5),E CHAR(5),F CHAR(5),G CHAR(5),H CHAR(5))INSERT INTO @Z SELECT @F,@H,@F,@H,@G,@H,@G,''WHILE @E<=@D BEGIN INSERT INTO @Z SELECT @I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT V FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT X FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT U FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT S FROM @)),'')SET @E+=1 END INSERT INTO @Z SELECT @F,@H,@J,@H,@G,'',@I,''SET @E=0WHILE @E<=@D BEGIN INSERT INTO @Z SELECT @I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT Y FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT Z FROM @)),''),@I,'',@I,''SET @E+=1 END INSERT INTO @Z SELECT @G,@H,@J,@H,@F,'',@I,''SET @E=0WHILE @E<=@D BEGIN INSERT INTO @Z SELECT @I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT T FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT W FROM @)),''),@I,'',@I,''SET @E+=1 END INSERT INTO @Z SELECT @G,@H,@G,@H,@F,@H,@F,''SELECT*FROM @Z

```

Less golfed version:

```
--finding the sets
DECLARE @D INT=@N,@E INT=0,@F CHAR='/',@G CHAR='\',@H CHAR='-',@I CHAR='|',@J CHAR='+'
DECLARE @ TABLE(Z INT,Y INT,X INT,W INT,V INT,U INT,T INT,S INT)
INSERT INTO @(Z)
SELECT A.P FROM @A A JOIN @B B ON A.P=B.P JOIN @C C ON A.P=C.P
INSERT INTO @(Y)
SELECT A.P FROM @A A JOIN @B B ON A.P=B.P LEFT JOIN @C C ON A.P=C.P WHERE C.P IS NULL
INSERT INTO @(X)
SELECT C.P FROM @C C JOIN @A A ON C.P=A.P LEFT JOIN @B B ON C.P=B.P WHERE B.P IS NULL
INSERT INTO @(W)
SELECT B.P FROM @B B JOIN @C C ON B.P=C.P LEFT JOIN @A A ON B.P=A.P WHERE A.P IS NULL
INSERT INTO @(V)
SELECT A.P FROM @A A LEFT JOIN @B B ON A.P=B.P LEFT JOIN @C C ON A.P=C.P WHERE C.P IS NULL AND B.P IS NULL
INSERT INTO @(U)
SELECT C.P FROM @C C LEFT JOIN @A A ON C.P=A.P LEFT JOIN @B B ON C.P=B.P WHERE B.P IS NULL AND A.P IS NULL
INSERT INTO @(T)
SELECT B.P FROM @B B LEFT JOIN @C C ON B.P=C.P LEFT JOIN @A A ON B.P=A.P WHERE A.P IS NULL AND C.P IS NULL
WHILE @N>=0
BEGIN
    INSERT INTO @(S)
    SELECT @N WHERE @N NOT IN(SELECT*FROM @A UNION SELECT*FROM @B UNION SELECT*FROM @C)
    SET @N-=1
END

--displaying the venn diagram
DECLARE @Z TABLE(A CHAR(5),B CHAR(5),C CHAR(5),D CHAR(5),E CHAR(5),F CHAR(5),G CHAR(5),H CHAR(5))
INSERT INTO @Z
SELECT @F,@H,@F,@H,@G,@H,@G,''
WHILE @E<=@D
BEGIN
    INSERT INTO @Z
    SELECT @I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT V FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT X FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT U FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT S FROM @)),'')
    SET @E+=1
END
INSERT INTO @Z
SELECT @F,@H,@J,@H,@G,'',@I,''
SET @E=0
WHILE @E<=@D
BEGIN
    INSERT INTO @Z
    SELECT @I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT Y FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT Z FROM @)),''),@I,'',@I,''
    SET @E+=1
END
INSERT INTO @Z
SELECT @G,@H,@J,@H,@F,'',@I,''
SET @E=0
WHILE @E<=@D
BEGIN
    INSERT INTO @Z
    SELECT @I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT T FROM @)),''),@I,ISNULL((SELECT CONVERT(CHAR,@E,5) WHERE @E IN(SELECT W FROM @)),''),@I,'',@I,''
    SET @E+=1
END
INSERT INTO @Z
SELECT @G,@H,@G,@H,@F,@H,@F,''
SELECT*FROM @Z

```
> 2 votes

---
Tags: code-golf, graphical-output, set-theory
---


# Question
Title: Where are the runs in this infinite string? (CCCCCC Found!)
Starting with the string `ABC`, consider the result of repeatedly appending the last half of itself to itself (using the larger half if the length is odd).

We get the progression:

```
ABC
ABCBC
ABCBCCBC
ABCBCCBCCCBC
ABCBCCBCCCBCBCCCBC
etc...

```

Let `S` represent the resulting infinite string (or sequence) that results as this procedure is repeated forever.

# Goal

The goal in this code challenge is to find the index of the first occurrence of runs of `C`'s in `S`.

It's easy at first: `C` first occurs at index `2`, `CC` at `4`, `CCC` at `7`, `CCCC` at `26`, but `CCCCC` is all the way at index `27308`! After that my memory runs out.

The winner will be the submission that correctly generates the most run indices (in order, starting at `C`). You can use any sort of algorithm but be sure to explain it if you aren't using basic brute force. The input and output can be in any easy to understand format.

**Important Note:** I do not officially know whether or not `S` actually contains all runs of `C`'s. This question is derived from this one on the Mathematics Stack Exchange, in which the author hasn't found `CCCCCC` either. I'm curious if anyone here can. (That question is in turn based on my original question on the topic.)

If you can prove that not all runs of `C` occur in `S` then you will win automatically since this question will no longer be valid. If no one can prove that nor find `CCCCCC` then the winner will be the person who can get the highest lower bound on the index of `CCCCCC` (or whatever the largest unsolved run is if `CCCCCC` is found).

**Update:** Humongous kudos to isaacg and r.e.s. who have found `CCCCCC` at the astronomical index of 2.124\*10^519. At this rate I can't imagine finding `CCCCCCC` with any method that relies on brute force. Good work guys!

# Answer
> 22 votes
# CCCCCC found at 2.124\*10^519.

Precise index is 2124002227156710537549582070283786072301315855169987260450819829164756027922998360364044010386660076550764749849261595395734745608255162468143483136030403857241667604197146133343367628903022619551535534430377929831860918493875279894519909944379122620704864579366098015086419629439009415947634870592393974557860358412680068086381231577773140182376767811142988329838752964017382641454691037714240414750501535213021638601291385412206075763857490254382670426605045419312312880204888045665938646319068208885093114686859061215

Found by r.e.s., using the (old version of) code below, after 3.5 hours of searching.

Around that index, the string is: `...BCCBCBCCCBCCCCCCBCCB...`

To verify, change the indicated line in the code below to start at 2946, instead of 5. Verification takes 20 seconds.

**Update: Improved program. Old program searched ~10x more locations than necessary.**

New version finds the `CCCCCC` in only 33 minutes.

How the code works: Basically, I only look at the regions which correspond to the ends of incremental strings, and calculate the letters by looking recursively back to the original string. Note that it uses a memo table, which may fill up your memory. Put a cap on the length of the memo table if necessary.

```
import time
import sys
sys.setrecursionlimit(4000)
ULIMIT=4000
end_positions=[]
current_end=2
while len(end_positions)<ULIMIT+3:
    end_positions.append(current_end)
    next_end=((current_end+1)*3+1)//2-1
    current_end=next_end
memo={}
def find_letter(pos):
    if pos in memo:
        return memo[pos]
    if pos<3:
        return 'ABC'[pos]
    for end_num in range(len(end_positions)-1):
        if pos>end_positions[end_num] and pos<=end_positions[end_num+1]:
            delta=end_positions[end_num+1]-end_positions[end_num]
            if len(memo)>5*10**6:
                return find_letter(pos-delta)
            memo[pos]=find_letter(pos-delta)
            return memo[pos]
time.clock()
for end_num in range(5,ULIMIT+1): # This line.
    diff = 1 # Because end_num is guaranteed to be a C
    while True:
        last_letter=find_letter(end_positions[end_num]+diff)
        if not last_letter=='C':
            break
        diff+=1
    if end_num%100==0:
        pos_str=str(end_positions[end_num])
        print(end_num,'%s.%s*10^%i'%(pos_str[0],pos_str[1:5],len(pos_str)-1),
        len(memo),diff,time.clock())
    if diff>=6:
        print(end_num,end_positions[end_num],diff,time.clock())

```

Current max searched to: 4000 iterations

`CCCCCC` found at iteration(s): 2946

# Answer
> 12 votes
### CCCCCC found at 2.124\*10^519.

The following ruby code was used to search for `CCCCCC`.

```
SEARCH = 6

k = [5,3]

getc=->i{
  j=i
  k.unshift(k[0]+(k[0]+1)/2)while(k[0]<=j)
  k.each_cons(2){|f,g|j-=f-g if j>=g}
  "ABC"[j]
}

while true
  x=k[0]
  x-=1 while getc[x]=="C"
  x+=1
  l=1
  l+=1 while getc[x+l]=="C"

  break if l>=SEARCH
end

puts x
puts (x-14..x+l+13).map{|i|getc[i]}*""

```

The index is the same as in @isaacg's answer.

The runtime of above code for 6 is in the order of ten seconds on my computer. Nevertheless, it is still search for an answer for `CCCCCCC` (if you want to try it yourself set constant `SEARCH` to `7`).

You can use `getc` to find the character at a specific position `i` as it is done in the last line where the string around the index is printed.

# Answer
> 5 votes
(Not an answer, but too long for a comment.)

The following is a Python translation of @Howard's Ruby program (sped up by a factor near 3 by having only one `getc` in the search loop). On my system, this finds the first C^6 in 3 seconds. In 93 hours, it finds no C^7 in 231,000 iterations, so the first C^7 (if it exists) must occur after the leftmost 10^40677 positions in the infinite string.

```
import time

L = [5, 3]      #list grows "backwards" (by insertion on the left)

def getc(i):    #return the letter at index i
    while L[0] <= i: L.insert(0,L[0] + (L[0] + 1)//2)
    for k in range(len(L)-1):
        if i >= L[k+1]: i -= L[k] - L[k+1]
    return 'abc'[i]

def search(k):  #find the first occurrence of c^k
    start = time.time()
    iter = 0
    while True:
        iter += 1
        if iter % 1000 == 0: print iter, time.time()-start
        p = L[0] - 1
        l = 1
        while getc(p+l)=='c': l += 1
        if l == k: break
    return p, iter, time.time()-start

k = 6

(indx, iter, extime) = search(k)
print 'run length:', k
print 'index:', indx, '    (',len(str(indx)),'digits )'
print 'iteration count:', iter
print 'neighborhood:', ''.join([getc(i) for i in range(indx-1,indx+k+10)])
print 'execution time:', extime

```

---
Tags: code-challenge, string
---


# Question
Title: Congratulations on getting 10,000 reputation!
After @MartinBüttner achieved exactly 10,000 reputation, we now have three full rows of 10k users on the users page! Now, since we're all programmers here, we like to automate things instead of doing them manually. Your challenge is to write a program to automatically congratulate new 10k users.

## Specification

### Input

The input will be `n` lines of space-separated numbers. (If you would like, you may also take a single comma-separated list of space-separated numbers, if that makes your code shorter.) For example:

```
10 20 30 40 50
15 25 35 45 55
20 30 40 50 60

```

Or:

```
10 20 30 40 50,15 25 35 45 55,20 30 40 50 60

```

Each list of numbers represents a list of users' reputation values on a single day.

### Output

The output will be the same amount of `n` lines (or a comma-separated list of the same length). Each line / list item will be:

* `:D` if there was a user whose reputation just became \>= 10,000.
    + Multiple space-separated `:D`s if there were multiple users who met or passed the 10,000 rep count. For example, `:D :D :D` for 3 new 10k users.
* `:(` and then halt further output if the input is ambiguous or impossible (more on this in the next section).
* nothing if neither of these conditions is true.

### Ambiguity

It is possible that the input is ambiguous. For the purposes of this challenge, we assume that:

* The reputation cap is 200 per day, ignoring accepts and bounties and the like for the sake of the challenge.
* Users may not lose reputation (again for simplicity and for the challenge).

Input is considered ambiguous when it is impossible to determine which reputation values correspond to which user. For example, in the input `10 20,30 40`, you can't tell whether the 10-rep user became the 30-rep user or the 40-rep user.

Input is considered impossible when the users from one day could not possibly have become the users from the next day. For example, in the input `10 20,310 320`, this situation is clearly impossible because the users could not have gained 300 reputation in a day. Users losing reputation is also impossible.

### Edge cases

* The initial reputation values can start at anything (i.e. a user can start with 1337 reputation).
* There is no output for the first line / list item.
* The input will always be syntactically valid, meaning that the reputation values will always be positive integers, there will always be the same amount of reputation values per line / list item, etc.
* The reputation values are not sorted; they may be in any order.

## Test cases

Input: `9900,10000`
Output: `:D`

Input: `9900 9950 9910,10100 9950 9910,10300 10150 10110`
Output: `:D,:D :D`

Input: `10 20 30,42 10 20,10 242 20,442 42 10,0 0 0,442 42 10`
Output: `,,,:(`

Input: `10 20,15 25,15 25`
Output: `,,`

Input: `9999 9998 9997,10000 9998 9997,10000 10000 9997,10300 10000 10000`
Output: `:D,:D,:(`

Input: `100,90,80,70`
Output: `:(`

Input: `10000 10000 10000 9999,10000 10000 10000 10000,10010 10020 10030 10040`
Output: `:D,:(`

Input: `9999 9998 9997 9996,10196 10197 10198 10199,10399 10199 10197 10196`
Output: `:D :D :D :D,`

# Answer
> 12 votes
## Ruby, 209 bytes

**Edit:** I switched to Ruby which shortened this by about 30%. See the edit history for the original Mathematica version. I suppose the main savings come from Ruby's `permutation` not ignoring switched positions of identical elements (which I had to trick Mathematica into).

This uses the newline-separated format.

```
gets.split('
').map{|s|s.split.map &:to_i}.each_cons(2){|a,b|a.permutation.map{|q|q.zip(b).map{|x,y|y-x}}.reject{|d|d.any?{|x|x<0||x>200}}.size!=1?abort(':('):(puts':D '*(a.count{|d|d<1e4}-b.count{|d|d<1e4}))}

```

The gist is this:

* Get all consecutive pairs of days.
* Get all permutations of the former day, and subtract each of these from the current day.
* Ditch all results which contain differences that are negative or greater 200.
* If the number of remaining permutations isn't 1, output `:(`.
* Otherwise, output as many `:D` as there are new 10k users.
* At the end, drop all days after the first `:(`.

Less golf:

```
gets.split("\n").map{|s|
  s.split.map &:to_i
}.each_cons(2){|a,b|
  a.permutation.map{|q|
    q.zip(b).map{|x,y|
      y-x
    }
  }.reject{|d|
    d.any?{|x|
      x<0||x>200
    }
  }.size!=1 ? abort(':(') : (puts ':D '*(a.count{|d|d<1e4}-b.count{|d|d<1e4}))
}

```

I think that's one beautiful chain of enumerators. :)

PS: Is it weird that *I* was the first one to submit an answer to this?

# Answer
> 6 votes
# Haskell, ~~254 249 244 232~~ 228

```
import Data.List
t=m(9999<)
p(a:b:r)=(a,b,r)%(filter(all(`elem`[0..200]))$nub$m(zipWith(-)b)$permutations a)
p _=""
(a,b,r)%(_:[])=(concat$m(const":D ")$t b\\t a)++'\n':p(b:r)
_%_=":("
m=map
main=interact$p.m(m read.words).lines

```

A little explanation: The algorithm is very similar to that used by MartinBüttner, except the `nub` that I spent some thought on. Note that a list difference is used for working out how many more reputation values are 10000 or larger on day n+1 compared to day n: `t b\\t a`.

I also agree with MartinBüttner on the interpretation of the specs and that some of the examples above are wrong, even to the point that example #2 is wrong (should be `:(`).

---
Tags: code-golf
---


title: Write a book writer

text:
# Question
Title: Write a book writer
Here is a fairly simple ASCII depiction of an open book:

```
|\
| \
|  \
|   \
|    \__________
|    ||         |
|    || Lorem i |
\    || psum do |
 \   || lor sit |
  \  ||  amet,  |
   \ || consect |
    \||_________|

```

Notice that the text portion is only on the right page and is 7 characters wide by 5 tall. Also notice that the top edge of the book has 5 backslashes and 10 underscores. The 10 comes from the text width plus 3 and the 5 is half of 10.

Using the same scaling format we can resize the book to have a text area *w* characters wide and *h* high, where *w* is any **odd** positive integer and *h* is any positive integer.

Some *w*×*h* books: 1×1, 1×2, 3×2

```
                    |\
          |\        | \
|\        | \____   |  \______
| \____   | ||   |  |  ||     |
| ||   |  | || L |  \  || Lor |
\ || L |  \ || o |   \ || em  |
 \||___|   \||___|    \||_____|

```

The number of underscores at the top is always *w*+3 and the number of backslashes is always (*w*+3)/2.

# Goal

Write a progam that takes a filename and *w* and *h* as command line arguments, and outputs a book with those text dimensions to stdout, displaying the contents of the file.

When the file has more text than will fit in one page the `N` key should print the next page and `B` should go back a page. Nothing should happen if `B` is pressed from the first page or `N` is pressed from the last page. The program should stop when the `Q` key is hit.

# Example

Suppose `f.txt` contains `Lorem ipsum dol?` and the user has pressed the key sequence `N N B N N Q`. The program should run something like this:

```
>>> bookmaker f.txt 3 2
|\
| \
|  \______
|  ||     |
\  || Lor |
 \ || em  |
  \||_____|

|\
| \
|  \______
|  ||     |
\  || ips |
 \ || um  |
  \||_____|

|\
| \
|  \______
|  ||     |
\  || dol |
 \ || ?   |
  \||_____|

|\
| \
|  \______
|  ||     |
\  || ips |
 \ || um  |
  \||_____|

|\
| \
|  \______
|  ||     |
\  || dol |
 \ || ?   |
  \||_____|

>>>

```

**Notice that there is a newline after every book and no trailing spaces. This is required.**

# Notes

* You may assume the file only contains printable ASCII characters (hex 20 to 7E).
* Print one character in each available spot, regardless of word boundaries.
* *w* and *h* are **optional** arguments that default to 7 and 5 respectively. Your program will either be given neither or both. (You may assume input is always well formed.)
* Fill any empty text space on the last page with spaces.
* `Q` should still be required to quit if there is only one page.

# Winning

The shortest program in bytes after bonuses are applied wins.

**Bonuses**

* Remove leading spaces so that every line starts with a word (or word segment). e.g. `| amet, |` in the first example would become `| amet, c |`. (-30 bytes)
* Clear the screen of previously drawn books after `N` or `B` is pressed (and `T` if you do the bonus after this) so the book looks like its changing pages in place. (-20 bytes)
* Make the `T` key instantly toggle between the text being drawn from left-to-right top-to-bottom (the default), to top-to-bottom left-to-right. If you did the first bonus it should work for columns in the top-to-bottom mode. (-100 bytes)

So for example:

```
|\
| \
|  \______
|  ||     |
\  || Lor |
 \ || em  |
  \||_____|

```

becomes

```
|\
| \
|  \______
|  ||     |
\  || Lrm |
 \ || oe  |
  \||_____|

```

# Answer
## C# 535bytes

*Score is 655bytes of code -20byte bonus for clearing, and -100byte bonus for T key... I think, can't say I'm sure I haven't missed something in the spec*

I may try and collapse the loops by having the W method return the s argument, but that would require effort, so no promises.

Golfed code:

```
using C=System.Console;using K=System.ConsoleKey;class P{static void W(int x,int y,string s){C.SetCursorPosition(x,y);C.Write(s);}static void Main(string[]a){int b=a.Length,w=b>0?int.Parse(a[0]):7,h=b>1?int.Parse(a[1]):5,p=0,i,j,o,T=1;var F=System.IO.File.ReadAllText("f.txt");b=(w+3)/2;S:C.Clear();for(i=0;i<w+3;i++){W(o=i+b+1,b-1,"_");W(o,h+b+1,"_");}for(i=0;i<h+2;){W(0,i,"|");W(b,o=i+++b,"||");W(b+w+4,o,"|");}for(i=0;i<b;){W(i+1,i,"\\");W(i,++i+h+1,"\\");}for(i=0;i<w;i++)for(j=0;j<h;)if((o=T>0?j++*w+p+i:i*h+p+j++)<F.Length)W(i+b+3,j+b,F[o]+"");K k=C.ReadKey(1>0).Key;p+=k==K.N&p<F.Length-w*h?w*h:k==K.B&p>0?-w*h:0;T=k!=K.T?T:-T;if (k!=K.Q)goto S;}}

```

Formatted a bit:

```
using C=System.Console;
using K=System.ConsoleKey;

class P
{
    static void W(int x,int y,string s)
    {
        C.SetCursorPosition(x,y);
        C.Write(s);
    }

    static void Main(string[]a)
    {
        int b=a.Length,w=b>0?int.Parse(a[0]):7,h=b>1?int.Parse(a[1]):5,p=0,i,j,o,T=1;
        var F=System.IO.File.ReadAllText("f.txt");
        b=(w+3)/2;

    S:
        C.Clear();

        for(i=0;i<w+3;i++)
        {
            W(o=i+b+1,b-1,"_");
            W(o,h+b+1,"_");
        }

        for(i=0;i<h+2;)
        {
            W(0,i,"|");
            W(b,o=i+++b,"||");
            W(b+w+4,o,"|");
        }

        for(i=0;i<b;)
        {
            W(i+1,i,"\\");
            W(i,++i+h+1,"\\");
        }

        for(i=0;i<w;i++)
            for(j=0;j<h;)
                if((o=T>0?j++*w+p+i:i*h+p+j++)<F.Length)
                    W(i+b+3,j+b,F[o]+"");

        K k=C.ReadKey(1>0).Key;
        p+=k==K.N&p<F.Length-w*h?w*h:k==K.B&p>0?-w*h:0;
        T=k!=K.T?T:-T;
        if (k!=K.Q)
            goto S;
    }
}

```
> 4 votes

# Answer
# Java, ~~1039~~ ~~1001~~ ~~993~~ ~~953~~ 946

With bonus: Remove leading spaces (-30 bytes) -\> **~~1009~~ ~~971~~ ~~963~~ ~~923~~ 916**

Clearing the screen is not worth it with java (except if I just print a couple of newlines. But then the user has to use the correct console size)

Code:

```
import java.io.*;import java.util.*;class B {static int w=7,h=5,p,l;static String t="",o,u=" ",y="\\";public static void main(String[]c)throws Exception{if(c.length>1){w=Integer.valueOf(c[1]);h=Integer.valueOf(c[2]);}Scanner s=new Scanner(new FileReader(c[0]));while(s.hasNext()){t+=s.nextLine();}l=t.length();s = new Scanner(System.in);while(true){int q=w+3,z=q/2,i=0,j=0,a=w*h;o="";for(;i<z;i++)o+="\n|"+r(u,i)+y;o+=r("_", q);for(;j<h+2-z;j++){o+="\n|"+r(u,i-1)+"||";if(j==0)o+=r(u,w+2);else o+=u+t()+u;o+="|";}for(;i>0;i--){o+="\n"+r(u,z-i)+y+r(u,i-1)+"||";if(i>1)o+=u+t()+" |";}o+=r("_",w+2)+"|";System.out.print(o);switch(s.next().charAt(0)){case'Q':return;case'B':p=p>a?p-2*a:p-a;break;case'N':p=p>l?p-a:p;}}}static String t(){int e=p+w>l?l:p+w;String r="";if(p<=e)r=t.substring(p,e);r=r.replaceAll("^\\s+","");int y=r.length();p+=w;return y==w?r:r+r(u,w-y);}static String r(String s,int i){return new String(new char[i]).replace("\0",s);}

```

Pretty:

```
import java.io.*;import java.util.*;
class B {
    static int w=7,h=5,p,l; // w = text width, h = text height, p = current position in text
    static String t="",o,u=" ",y="\\";
    public static void main(String[]c)throws Exception{
        // get w and h of text, default to 7x5
        if(c.length>1){w=Integer.valueOf(c[1]);h=Integer.valueOf(c[2]);}
        // read file
        Scanner s=new Scanner(new FileReader(c[0]));while(s.hasNext()){t+=s.nextLine();}
        l=t.length();
        // read input
        s = new Scanner(System.in);
        while(true){
            // print book
        int q=w+3,z=q/2,i=0,j=0,a=w*h; // q = number of underscores at the top, z = number of backslashes
        o="";
        // print top of book
        for(;i<z;i++)o+="\n|"+r(u,i)+y;
        o+=r("_", q);
        // print middle of book (hp-z lines). right now: i = z -1
        for(;j<h+2-z;j++){o+="\n|"+r(u,i-1)+"||";if(j==0)o+=r(u,w+2);else o+=u+t()+u;o+="|";}
        // print bottom of book
        for(;i>0;i--){o+="\n"+r(u,z-i)+y+r(u,i-1)+"||";if(i>1)o+=u+t()+" |";}
        o+=r("_",w+2)+"|";
        System.out.print(o);
        // user input
            switch(s.next().charAt(0)){
                case'Q':return;
                case'B':p=p>a?p-2*a:p-a;break;
                case'N':p=p>l?p-a:p;
            }
        }
    }

    /** return w characters of string t, from given position p. increase p*/
    static String t(){
        int e=p+w>l?l:p+w;
        String r="";
        if(p<=e)r=t.substring(p,e);
        r=r.replaceAll("^\\s+",""); // remove leading spaces (cost:28 chars)
        int y=r.length();
        p+=w;
        return y==w?r:r+r(u,w-y);
    }
    static String r(String s,int i){return new String(new char[i]).replace("\0",s);} // repeat given string i times

```

If the program does not have to run forever, I could also save some bytes by removing the while loop and just calling main.

This is not optimal, but it's a start.
> 4 votes

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


# Question
Title: Calculate the probability of seeing a landmark when starting at a given point and walking straight in a random direction
**Input** 5 integers: Landmark `X` & `Y`, Starting Point `X` & `Y`, and View Distance Radius `D`

**Output** 1 double: % chance of coming within `D` of Landmark (`X`,`Y`) ("seeing") when walking straight in a random direction from Starting Point (`X`,`Y`).

Assume that "random direction" shall be a direction uniform on \[0,2π\], the land is flat, and of course the 'hiker' never turns after he begins moving.

**Example:** If landmark is at (10,10), starting point is (5,5), and view distance is 20 then the output would be 100% as no matter which direction you walk the landmark will be immediately visible.

# Answer
## CJam *-41* *-40* *-39* *-38/35* **31/26**

This seems to work. It is my first attempt at CJam and/or codegolf. Run the code at http://cjam.aditsu.net/. In the section called input just place the variables as integers delimited with spaces in the input block in this order: distance D, landmark x, starting x, landmark y, starting y (for example 20 10 5 10 5). I had posted a previous one based on a misunderstanding of the equation that has been resolved. I also had been returning answers as probability ratios rather than percentages. **Note: the second code has only 31 characters** but combines alot from another user's CJam code.

```
ri{riri- 2#}:U;UU+.5#/mSP/:A.5<A1?e2

r{~riri-_*}_~+mq/mSP/:A.5<A1?e2

```

Accuratish one without arcsine being directly called (44 characters):

```
ririri- 2#riri- 2#+ .5#/:A1<AA3#6/+P/1?100*

```

Even more accurate (52 characters):

```
ririri- 2#riri- 2#+ .5#/:A1<AA3#6/+A5#40/3*+P/1?100

```

Update:

The absolute best I've written is 26 characters. I've still learned alot by watching professorfish's attempts but the crux is mine. I assumes (potentially incorrectly) that if you can see the landmark if it is closer (not closer than or equal to) your sight radius.

```
1r{~riri-_*}_~+mq/mSP/e<e2

```
> 3 votes

# Answer
# Haskell, ~~65~~ 63

```
import Data.Complex
(s,l)%d=100*min(asin(d/magnitude(s-l))/pi)1

```

Use like `(xstart:+ystart, xlandmark:+ylandmark) % distance`. Gives result in percent. Why is it so expensive to load modules in Haskell?!?

Note that there is no if/then/else, pattern matching, etc. in this code, `min` does the magic.
> 6 votes

# Answer
# CJam, ~~44 40 38~~ 37

First CJam script! Uses the method on the Math.SE answer here.

Supports non-integer inputs as well, at no extra character cost.

```
rd{rdrd-_*}:U~U+mq/_1<{mSP/}{;1}?100*

```

Interpreter at cjam.aditsu.net.

## Order of inputs

The inputs are given in this order, on STDIN, separated by spaces:

1. View Distance Radius
2. Landmark X
3. Starting Point X
4. Landmark Y
5. Starting Point Y
> 2 votes

# Answer
# Haskell — ~~72 70 69~~ 68

I think this satisfies the question, but if not please leave a comment and I'll do my best to fix it:

```
w s y l z d|r<d=100|0<1=asin(d/r)/pi*100where r=sqrt$(l-s)^2+(z-y)^2

```
> 1 votes

# Answer
# Python - 73

```
from math import*
f=lambda l,s,d:(abs(l-s)<=d or asin(d/abs(l-s))/pi)*100

```

`l` is a complex number (e.g. `5 + 5j`) describing the landmark position, `s` describes the start position and `d` is the view distance, for the example from the question call `f` as follows: `f(5 + 5j, 10 + 10j, 20)`
> 1 votes

---
Tags: code-golf, probability-theory
---


title: Let us create a sonnet quine!

text:
# Question
Title: Let us create a sonnet quine!
There are programs that will output its source code to standard output and do nothing else. They also access no external output. This type of program is known as a quine, and is a common code challenge.

There are poems that have the rhyme scheme a-b-a-b, c-d-c-d, e-f-e-f, g-g. They have 14 lines. They are usually recited in iambic pentameter. They are called sonnets.

You are to write a program/poem that is both a quine and a sonnet.

1. When saying lines, it is recommended that you only say all characters except for: whitespace and `,()[]_"'`. This is flexible depending on the language though.
2. Iambic Pentameter means 10 syllables, starting unstressed, and then alternating between stressed and unstressed. This is optional, but will mean more votes.
3. Comments are discouraged, especially to complete rhymes (although comments are very much encouraged if they can be incorporated with the code in the poem in a way that produces dramatic effect.)
4. Cruft is discouraged.

Voters, use the four above guidelines when voting. This is a popularity contest, so the program with the most votes wins.

# Answer
# Ruby

```
s = [[/t{1}he_way/,'to_a'],[/\*j{1}ewel/,'*rule']].to_a
puts <<'-'.*(2).tap { |code| s.each { |rule| code.sub! *rule } }, '-'
s = [[/t{1}he_way/,'to_a'],[/\*j{1}ewel/,'*rule']].the_way
puts <<'-'.*(2).tap { |code| s.each { |rule| code.sub! *jewel } }, '-'
-
s = [[/t{1}he_curse/,'reverse'],[/\*c{1}raze/,'*phrase']].reverse
puts <<'-'.*(2).tap { |code| s.each { |phrase| code.sub! *phrase } }, '-'
s = [[/t{1}he_curse/,'reverse'],[/\*c{1}raze/,'*phrase']].the_curse
puts <<'-'.*(2).tap { |code| s.each { |phrase| code.sub! *craze } }, '-'
-
s = [[/r{1}eject/,'collect'],[/\*b{1}ird/,'*word']].collect
puts <<'-'.*(2).tap { |code| s.each { |word| code.sub! *word } }, '-'
s = [[/r{1}eject/,'collect'],[/\*b{1}ird/,'*word']].reject
puts <<'-'.*(2).tap { |code| s.each { |word| code.sub! *bird } }, '-'
-
puts <<'-'.*(2).tap { |code| [[/\*l{1}augh/,'*half']].each { |half| code.sub! *half } }, '-'
puts <<'-'.*(2).tap { |code| [[/\*l{1}augh/,'*half']].each { |half| code.sub! *laugh } }, '-'
-

```

Don't pronounce the dashes, they're just there to delimit stanzas. Scansion's not perfect but decent.
> 6 votes

---
Tags: popularity-contest, restricted-source, quine, source-layout
---


title: Raise to the Power

text:
# Question
Title: Raise to the Power
### Challenge

Challenge is writing a program that takes a **positive** numbers `a` and a **nonzero** number `b` and outputs `a^b` (a raised to the power b). You can only use `+ - * / abs()` as mathematical functions/operators. These can only be applied to scalar values, but not to whole lists or arrays.

Examples:

```
1.234 ^ 5.678 = 3.29980
4.5   ^ 4.5   = 869.874
4.5   ^-4.5   = 0.00114959

```

Relevant: http://xkcd.com/217/

### Details

You can write a function or a similar construct for using in console. If you cannot use console input you can assume that both numbers are saved in variables and ouptut via standard output or writing to a file. The output has to be correct to at least 4 significat digits. You can assume that both `a` and `b` are nonzero. A runtime of significantly more than 1 minute is not acceptable. The least number of bytes will win. Please explain your program and your algorithm.

EDIT: Only **positive bases** have to be considered. You can assume `a>0`. **Be aware that both numbers do not have to be integers!!!**

# Answer
# Python, 77

As with some other answers this is based on log and exp. But the functions are computed by numerically solving ordinary differential equations.

```
def f(a,b,y=1):
 if a<1:a=1/a;b=-b
 while a>1:a/=1e-7+1;y*=b*1e-7+1
 return y

```

Does it satisfy the requirements? For the examples in the question, yes. For large a, it will take a very long time. For large a or b, it will become inaccurate.

Examples:

```
a            b            f(a, b)      pow(a, b)      <1e-5 rel error?
       1.234        5.678       3.2998       3.2998   OK
         4.5          4.5      869.873      869.874   OK
         4.5         -4.5   0.00114959   0.00114959   OK
         0.5          0.5     0.707107     0.707107   OK
         0.5         -0.5      1.41421      1.41421   OK
          80            5  3.27679e+09   3.2768e+09   OK
     2.71828      3.14159      23.1407      23.1407   OK

```

Update: flawr asked for more detail on the maths so here you go. I considered the following initial value problems:

* x'(t) = x(t), with x(0) = 1. The solution is exp(t).
* y'(t) = by(t), with y(0) = 1. The solution is exp(bt).

If I can find the value of t such that x(t) = a, then I'll have y(t) = exp(bt) = a^b. The simplest way to numerically solve an initial value problem is Euler's method. You compute the derivative the function is supposed to have, and then take a, step, in the *direction* of the derivative, and *proportional* to it, but scaled by a tiny constant. So that's what I do, take tiny steps until x is as big as a, and then see what y is at that time. Well, that's the way I thought of it. In my code, t is never explicitly computed (it is 1e-7 * the number of steps of the while loop), and I saved some characters by doing the calculations for x with a instead.
> 3 votes

# Answer
# JavaScript (E6) 155 ~~174 191~~

**Edit 2** As suggested by @bebe, using recursive function (performe worse but shorter)
Slightly changed R function to avoid 'too much recursion'
Test suite added. The function performs well for bases \< 3000 and exponent in range -50..50.
**Edit** Golfed more and better precision

Any real number can be approximate with a rational number (and IEEE standard 'real' numbers store rationals in fact). Any rational number can be expressed as a fraction a/b with a and b integers. x^(a/b) is root b of (x^a) or (root b of x)^a. Integer exponentiation is quite easy by squaring. Integer root can be approximated using numerical methods.

**Code**

```
P=(x,e)=>(
  f=1e7,e<0&&(x=1/x,e=-e),
  F=(b,e,r=1)=>e?F(b*b,e>>1,e&1?r*b:r):r,
  R=(b,e,g=1,y=1e-30,d=(b/F(g,e-1)-g)/e)=>d>y|d<-y?R(b,e,g+d,y/.99):g,
  F(R(x,f),e*f)
)

```

**Test** In FireFox or FireBug console

```
for (i=0;i<100;i++)
{
  b=Math.random()*3000
  e=Math.random()*100-50
  p1=Math.pow(b,e) // standard power function, to check
  p2=P(b,e)
  d=(p1-p2)/p1 // relative difference
  if (!isFinite(p2) || d > 0.001)
    console.log(i, b, e, p1, p2, d.toFixed(3))
}

```
> 6 votes

# Answer
# Haskell, 85 ~~90~~

Standard exp-log algorithm. Now with different name, shaving off a few more characters:

```
a%b|a>1=1/(1/a)%b|0<1=sum$scanl((/).((-b*foldr1(\n b->(1-a)*(b+1/n))c)*))1c
c=[1..99]

```

`raise` is now called `(%)`, or `%` in infix notation, even making its use consume fewer bytes: `4.5%(-4.5)`

The ungolfed version also uses just 172 bytes:

```
raise a b | a > 1     = 1 / raise (1/a) b
          | otherwise = expo (-b* ln (1-a))

ln x = foldr1 (\n a -> x*a+x/n) [1..99]

expo x = sum $ scanl ((/) . (x*)) 1 [1..99]

```
> 6 votes

# Answer
## JS (ES6), 103 bytes

```
t=(x,m,f)=>{for(r=i=s=u=1;i<1<<7+f;r+=s/(u=i++*(f?1:u)))s*=m;return r};e=(a,b)=>t(b,t(a,1-1/a,9)*b-b,0)

```

Examples :

```
e(1.234,5.678) = 3.299798925315965
e(4.5,4.5)     = 869.8739233782269
e(4.5,-4.5)    = 0.0011495918812070608

```

Use Taylor series.
`b^x = 1 + ln(b)*x/1! + (ln(b)*x)^2/2! + (ln(b)*x)^3/3! + (ln(b)*x)^4/4! + ...`
with natural logarithm approximation :
`ln(b) = (1-1/x) + (1-1/x)^2/2 + (1-1/x)^3/3 + (1-1/x)^4/4 + ...`

I used 128 iterations to compute `b^x` (more iterations is difficult due to factorial) and 262144 iterations for `ln(b)`
> 4 votes

# Answer
# golflua 120

I use the fact that

```
a^b = exp(log(a^b)) = exp(b*log(a))

```

and wrote my own `log` & `exp` functions. The values `a` and `b` need to be entered on newlines when run in the terminal:

```
\L(x)g=0~@ i=1,50 c=(x-1)/x~@j=2,i c = c*(x-1)/x$g=g+c/i$~g$\E(x)g=1;R=1e7~@i=1,R g=g*(1+x/R)$~g$a=I.r()b=I.r()w(E(b*L(a)))

```

Sample runs:

```
4.5, 4.5  ==> 869.87104890175
4.5, -4.5 ==> 0.0011495904124065
3.0, 2.33 ==> 12.932794624815
9.0, 0.0  ==> 1
2.0, 2.0  ==> 3.9999996172672

```

An ungolfed Lua version is,

```
-- returns log
function L(x)
   g = 0
   for i=1,50 do
      c=(x-1)/x
      for j=2,i do
         c = c*(x-1)/x
      end
      g = g + c/i
   end
   return g
end

-- returns exp
function E(x)
   g=1;L=9999999
   for i=1,L do
      g=g*(1+x/L)
   end
   return g
end

a=io.read()
b=io.read()

print(E(b*L(a)))
print(a^b)

```
> 3 votes

---
Tags: code-golf, math, restricted-source
---