title: Let's create random number genrator

text:
# Question
Title: Let's create random number genrator
The task is to make a function which returns random number, no build in functions allowed, returned value should be random or pseudo-random and no sequence allowed, no matter what the formula is and how scattered values are.

To simplify task, returned value should be 32-bit integer or float from range \[0; 1)

It is code golf, shortest code wins :)

# Answer
# CoffeeScript (16 bytes)

```
->new Date%2**32

```

This is awful random number generator, but if you wait enough, you can get any integer.
> 3 votes

---
Tags: code-golf
---


title: Do We Sink or Swim?

text:
# Question
Title: Do We Sink or Swim?
**The Problem**

A doomsday scenario is described by three numbers on a single line, `n`, `m`, and `p`. Following that line are `n` lines with `m` values per line. Each value represents the total units of water each cell can hold.

The following `p` lines describe the weather for the next `p` days. 1 unit of rain falls on a single cell each day. If the amount of water in a cell exceeds the amount it can hold, that cell floods. If multiple adjacent cells are at full capacity, they are treated as one cell that share common neighbors (think Minesweeper when you click on a group of blanks).

* A single middle cell has 4 neighbors
* Two adjacent, full capacity middle cells are treated as one cell that has 6 neighbors
* A single corner cell has 2 neighbors
* A single wall cell has 3 neighbors

When a cell floods, a flood event occurs. All excess water is evenly distributed to its neighbors. If that causes one or more neighbors to flood, then another flood event occurs. This continues until the water has settled, or the city has completely flooded.

**Example Input**

> 7 5 3
> 3 2 3 4 5
> 2 2 0 3 4
> 1 1 2 3 3
> 4 1 2 2 2
> 4 1 1 2 2
> 4 4 1 2 2
> 4 4 2 2 2
> 0 0
> 1 2
> 4 3

* `0 0` means it rained on row 1, col 1
* `1 2` means it rained on row 2, col 3 (which can hold zero water and immediately floods!)

After `p` days of rain, if the city is completely flooded, output **Sink**. Otherwise, output **Swim**.

**Example Output**

> Swim

**Assumptions**

* Input may be provided through stdin, read from "city.txt", or accepted as an argument. All three are allowed so as not to invalidate any answers already posted.
* Water capacities will be non-negative integers.

40+ teams of undergrad college students (from A&M, UT, LSU, Rice, Baylor, etc.) competing in a programming contest with a variety of languages available could not solve this problem in 5 hours. Because of that, I can't help but mention that there is a catch to this puzzle that makes the solution trivial. Shortest code still wins, because I am that confident that the shortest code will also solve the puzzle.

# Answer
# Golfscript, ~~37~~ 30 characters

New and improved, thanks to PeterTaylor for tips:

```
~](\(@*\(@@<{+}*>"SwimSink"4/=

```

**Explanation**:

```
Code                     -                                            - Stack
~]                       - parse input into an array of integers      - []
(                        - pop first number and put on stack          - [] 7
\(                       - \ swaps top two, then pop first num again  - 7 [] 5
@                        - bring 3rd down from stack to front         - [] 5 7
*                        - mult. this is grid size                    - [] 35
\(@                      - bring next # out - the days of rain        - [] 3 35
@                        - bring array out                            - 3 35 []
<                        - take first 35 elements out of array.
                           this extracts just the capacities and
                           consumes the rest                          - 3 []
{+}*                     - fold the array using plus - this sums the
                           entire thing                               - 3 86
<                        - greater-than comparison: 3 > 86?           - 0
"SwimSink"4/             - push a string and split it to groups of 4  - 0 ["Swim" "Sink"]

=                        - index into the array using the result of
                           the comparison. if rain > capacity, then
                           sink, else swim                            - "Swim"

```

Program then terminates, outputting the stack.

---

Old version + explanation:

```
[~](\(@*\(@{\(@\-}*\;0>"Sink""Swim"if

```

Same approach as Fors, just Golfscripted =). Can likely be made more efficient. Input is from stdin.

**Explanation**:

```
Code                     -                                            - Stack
[~]                      - parse input into an array of integers      - []
(                        - pop first number and put on stack          - [] 7
\(                       - \ swaps top two, then pop first num again  - 7 [] 5
@                        - bring 3rd down from stack to front         - [] 5 7
*                        - mult. this is grid size                    - [] 35
\(@                      - bring next # out - the days of rain        - [] 3 35
{                        - define a block which...
 \(@                     - brings next number out
 \-                      - swaps and subtracts 2nd down from top
}                                                                     - [] 3 35 {}
*                        - repeat that block 35 times. this ends up
                           pulling the capacities out one by one
                           and decrementing our number-of-days
                           number by each one                         - [] -84
\;                       - swap and kill the array to get rid of
                           unused input                               - -84
0>"Sink""Swim"if         - if the num > 0, evaluate to "Sink",
                           otherwise to "Swim"                        - "Swim"

```

Program then outputs the stack, which is just the answer.
> 16 votes

# Answer
# C: ~~100~~ ~~96~~ 95 characters

```
n,m;main(p){scanf("%d%d%d",&n,&m,&p);for(n*=m;n--;scanf("%d",&m))p-=m;puts(p>0?"Sink":"Swim");}

```

Five hours? Took me five minutes. :)

Aragaer, thank you for the simplifications! I did however rearrange the variable declarations and arguments to main, seeing as Clang throws an error if the second argument to main is of any other type than `char **`.
> 20 votes

# Answer
# Python, 4 lines, 175 characters

```
import sys
F=sys.stdin
n,m,p=[int(a) for a in F.readline().split()]
print("sink") if p > sum([sum(int(x) for x in F.readline().split()) for a in range(n)]) else print("swim")

```

Lol, I wonder if the 40+ teams ended up finding the catch... after working it out the hard way.
> 7 votes

# Answer
# J (50 char) and K (40) double feature

Turns out, as usual, these two have the exact same structure in their solutions, so they're both here. K is a whole lot shorter, though, which is a pleasant surprise.

```
>Sink`Swim{~(]<[:+/[+/@".@$+1!:1@#1:)/0 2{".1!:1]1

```

Explanation:

* `".1!:1]1` \- Read in the first line, and convert to integers.
* `(...)/0 2{` \- Take the items at index 0 and 2 (`n` and `p` respectively), and use them as the left and right arguments to the verb `(...)`, respectively.
* `+1!:1@#1:` \- Read in `n+p` lines.
* `[+/@".@$` \- Take (`$`) the first `n` rows (`[`), discarding the rest, and then convert to integers (`".`) and sum on each row (`+/`).
* `]<[:+/` \- Add together the row sums, and then compare this value to the right argument, `p`. We produce true if `p` is less than the sum.
* `>Sink`Swim{~` \- Select `Swim` if the above comprasion resulted in true, or `Sink` if false.

Usage:

```
   >Sink`Swim{~(]<[:+/[+/@".@$+1!:1@#1:)/0 2{".1!:1]1
7 5 3
3 2 3 4 5
2 0 3 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3
Swim

```

And now the K:

```
`Sink`Swim@{z<+//.:'x#0::'(x+z)#`}.. 0:`

```

Explained:

* `. 0:`` \- Read in a line of input, and convert to an array of integers.
* `{...}.` \- Use these three numbers `n m p` as the arguments `x y z` to this function.
* `0::'(x+z)#`` \- Create `x+z` copies of the input file handle ```, and then read in a line for each of them (`0::'`).
* `.:'x#` \- Take the first `x` items, and convert each to a vector of numbers.
* `z<+//` \- Sum the entire matrix together, and then test to see if it is greater than `z`.
* ``Sink`Swim@` \- Return `Sink` or `Swim` according to whether the test returned true.

Usage:

```
  `Sink`Swim@{z<+//.:'x#0::'(x+z)#`}.. 0:`
7 5 3
3 2 3 4 5
2 2 0 3 4
1 1 2 3 3
4 1 2 2 2
4 1 1 2 2
4 4 1 2 2
4 4 2 2 2
0 0
1 2
4 3
`Swim

```
> 6 votes

# Answer
## APL, 35

```
4↑'SwimSink'⌽⍨4×x[3]>+/{+/⎕}¨⍳1⌷x←⎕

```

Not sure if allowed but it stops accepting input after the "city"

`x←⎕` Takes input and store it in variable `x` (space-delimited numbers are interpreted as a numerical array)
`1⌷` Extract index 1 (APL arrays are one-based)
Generate an array from 1 to the argument (`1⌷x←⎕` in this case)
`¨` "Map" operation
`{+/⎕}` Take array from input and return the sum
`+/` Sum the array generated by the map operation
`4×x[3]>` Test if the sum \< `x[3]` (returns 1 or 0), then multiply 4
`'SwimSink'⌽⍨` Rotate the string `'SwimSink'` by that amount
`4↑` Finally, extract the first 4 characters of the string
> 6 votes

# Answer
# AWK, 70

```
n{for(;NF;NF--)s+=$NF;n--}NR==1{n=$1;p=$3}END{print p<s?"Swim":"Sink"}

```

This is an imrovement by laindir on my submission (86):

```
NR==1{h=$1;w=$2;r=$3;next}NR<=h{for(i=1;i<=w;++i)c+=$i}END{print(c>r?"Swim":"Sink")}

```
> 6 votes

# Answer
# CoffeeScript - 128 113

A function that takes the string as the only argument:

```
s=(l)->l=l.split /\n/;[n,m,p]=l[x=0].split /\s/;x+=c|0 for c in r.split /\s/ for r in l[1..n];`p>x?"Sink":"Swim"`

```
> 5 votes

# Answer
# SED, 128

It was fun to write a `sed` version of this. It has the following short-comings:

* It assumes the city has more than two columns, to easily recognise rain lines.
* It assumes that the capacity of each city is in the range 0-9.

Here it is:

```
1d
s/^. .$/R/
G
:a
s/[\n 0]//
/[2-9]/{s/^/C/
y/23456789/12345678/}
s/1/C/
s/0//
s/RC//
h
ta
${s/R//g
s/^Sink//
s/.*C$/Swim/
p}

```

Call with the `-n` flag.
> 4 votes

# Answer
# SWI-Prolog 79

If you don't mind the fact that this answer takes input by query, rather than via stdin:

```
s(A,L):-append(A,B),sumlist(B,C),length(L,D),(D>C->E='Sink';E='Swim'),print(E).

```

The answer doesn't validate input format, but I don't think it is a problem, since programming contest also doesn't require you to do so.

Sample query (using example in the question):

```
s([[3,2,3,4,5],
   [2,2,0,3,4],
   [1,1,2,3,3],
   [4,1,2,2,2],
   [4,1,1,2,2],
   [4,4,1,2,2],
   [4,4,2,2,2]],
  [(0,0),
   (1,2),
   (4,3)]).

```
> 3 votes

# Answer
# Python - 152

```
import numpy
n, m, p = map(int,raw_input('').split())
print 'swim' if p<numpy.sum(numpy.matrix(';'.join([raw_input('') for i in range(n)]))) else 'sink'

```
> 1 votes

# Answer
# Scala - 128

```
val a=readLine.split(' ')map(_.toInt);println(if((1 to a(0)map(x=>readLine.split(' ')map(_.toInt)sum)sum)>a(2))"swim"else"sink")

```

It might be possible to omit some parentheses or something but Scala is really fickle about punctuation and point-free style and () vs {} and whatnot.
> 1 votes

# Answer
# Javascript - 73 Characters

```
for(i=c=0,a=s.split(/\s/);i++<a[0]*a[1];)c+=a[2+i]*1;c>a[2]?"Swim":"Sink"

```

Assumes the input is in the variable `s` and outputs `Swim` or `Sink`.

**Example:**

From the original question - entering this into the browser console:

```
s="7 5 3\n3 2 3 4 5\n2 2 0 3 4\n1 1 2 3 3\n4 1 2 2 2\n4 1 1 2 2\n4 4 1 2 2\n4 4 2 2 2\n0 0\n1 2\n4 3";
for(i=c=0,a=s.split(/\s/);i++<a[0]*a[1];)c+=a[2+i]*1;c>a[2]?"Swim":"Sink"

```

Outputs:

```
Swim

```
> 0 votes

---
Tags: code-golf
---


title: Autoscale complex function

text:
# Question
Title: Autoscale complex function
**Context:** We are working on a complex image drawing program to produce mugs, t-shirts, and so on. Here is an example of such function

However, we are facing the following problem: Random generated functions are mostly white and black (where black is close to zero and white close to infinity). The idea of this contest is to find a number to scale all numbers so that corresponding colors are in the visible spectrum.

**Problem**

The input is, formatted the way you want:

* An array of double precision A\[1..n\] randomly sorted of positive numbers (\>0).
* An expected inclusive lower bound L \> 0
* An expected inclusive upper bound U \> 0

The expected output is

* A number `f` so if we multiply all elements of A by `f`, it maximizes the number of the new elements between L and U. If there are multiple solutions, `f` should be as close to 1 as possible.

Write a program computing `f` in a few operations as possible.

To check, post the result of your program on the following (sorted for convenience) input:

```
A = [0.01, 0.02, 0.5, 1 , 5, 9.5, 9.8, 15, 18, 20, 50, 100]
L = 1
U = 5

```

The result should be `f` = 0.25

**Winning conditions**: The winner will be the one with the best time complexity. If there are multiple algorithms of the same complexity, the fastest one will win. If your program is obfuscated or hard to read, please also attach an unobfuscated version with explanations.

# Answer
> 2 votes
## Perl O(n log n)

```
#!/usr/bin/env perl
use strict;
$^W=1;

# calculate_f ( <lower bound>, <upper bound>, <array reference> )
sub calculate_f ($$$) {
    my $L = shift;
    my $U = shift;
    my $A = shift;
    my $n = @$A;

    # Catch trivial cases:
    # * Upper bound is lower than lower bound,
    # * array is empty.
    # In both cases the result array is empty and the value
    # of f does not matter. Therefore we can return the
    # "optimum" value 1.
    return 1 if $U < $L or $n == 0;

    # The array is sorted. accordign to the manual page, Perl since 5.7
    # uses a "stable mergesort algorithm whose worst-case behaviour
    # is O(N log N).
    my @A = sort {$a <=> $b} @$A;

    # Array @R stores the length of ranges:
    # $R[$i] is the number of elements that form a valid
    # range of input numbers ($A[$i], ..., $A[$i + $R[$i] - 1])
    my @R;
    my $lu = $L / $U;
    my $ul = $U / $L;
    # find ( <upper value>, <left position>, <right position> )
    # The function looks for the largest input value below or equal
    # <upper value>. Invariant: The input value at <left position>
    # in the sorted array belongs to the range below <upper value>,
    # the input value at <right position> is larger than <upper value>.
    # It is a binary search: O(log n)
    sub find ($$$) {
        my $u = shift;
        my $left = shift;
        my $right = shift;
        return $left if $right <= $left + 1;
        my $next = int(($left + $right)/2);
        return find($u, $next, $right) if $A[$next] <= $u;
        return find($u, $left, $next);
    }
    for (my $i = 0; $i < $n; $i++) {
        my $a = $A[$i];
        my $u = $a * $ul;
        if ($A[$n-1] <= $u) {
            $R[$i] = $n - $i;
            next;
        }
        $R[$i] = find($u, $i, $n - 1) - $i + 1;
    }
    # Complexity is n times the loop body with the binary search: O(n log n).

    # In the next step the maximum number of a valid range is
    # obtained: O(n)
    my $max = 0;
    for (my $i = 0; $i < $n; $i++) {
        my $a = $R[$i];
        $max = $a if $a > $max;
    }
    print "(Debug) maximal number of elements in a valid range: $max\n";

    # Now each range is checked to find the optimum f
    my $f = 0;
    for (my $i = 0; $i < $n; $i++) {
        # ignore ranges with fewer elements
        next unless $R[$i] == $max;

        # print current range:
        print sprintf "(Debug) A[%d .. %d] = (%g .. %g)\n",
                $i, $i + $max - 1,
                $A[$i], $A[$i + $max - 1];

        # calculate f values based on the smallest/largest element
        my $f_lower = $L / $A[$i];
        my $f_upper = $U / $A[$i + $max - 1];
        # if 1 is in the middle of the f values, then return
        # optimal value
        return 1 if $f_lower <= 1 and $f_upper >= 1;

        # Now $f_lower and $f_upper are both smaller or both greater than 1.
        # A candidate for $f is selected from the current range
        # by using the value that is closer to 1.
        my $f_candidate = $f_lower < 1 ? $f_upper : $f_lower;
        print sprintf "(Debug) f_candidate = %g from (%g .. %g)\n",
                $f_candidate, $f_lower, $f_upper;

        # Compare the candidate with the current f
        if (not $f or abs($f_candidate - 1) < abs($f - 1)) {
            $f = $f_candidate;
        }
    }
    # Complexity is O(n), because the loop body is O(1).

    return $f;
}

my $f = calculate_f(1, 5, [
    0.01, 0.02, 0.5, 1 , 5, 9.5, 9.8, 15, 18, 20, 50, 100
]);

print "(Result) f = $f\n";

__END__

```

Example output:

```
(Debug) maximal number of elements in a valid range: 6
(Debug) A[4 .. 9] = (5 .. 20)
(Debug) f_candidate = 0.25 from (0.2 .. 0.25)
(Result) f = 0.25

```

**Algorithm** is explained in the comments. The input numbers are sorted with O(n log n). Then for each number its valid range is obtained, O(n log n), then the maximum number of elements in the range is found, O(n) and the best fitting f value is calculated, O(n).

**Complexity:** O(n log n)

---

## Older version with O(n2)

```
#!/usr/bin/env perl
use strict;
$^W=1;

# calculate_f ( <lower bound>, <upper bound>, <array reference> )
sub calculate_f ($$$) {
    my $L = shift;
    my $U = shift;
    my $A = shift;
    my $n = @$A;

    # Catch trivial cases:
    # * Upper bound is lower than lower bound,
    # * array is empty.
    # In both cases the result array is empty and the value
    # of f does not matter. Therefore we can return the
    # "optimum" value 1.
    return 1 if $U < $L or $n == 0;

    # The array is sorted. according to the manual page, Perl since 5.7
    # uses a "stable mergesort algorithm whose worst-case behaviour
    # is O(N log N)".
    my @A = sort {$a <=> $b} @$A;

    # Array @R stores the length of ranges for each element with
    # position $i in the sorted array, if the range starts with this
    # element:
    # $R[$i] is the number of elements that form a valid
    # range of input numbers ($A[$i], ..., $A[$i + $R[$i] - 1])
    my @R;
    my $lu = $L / $U;
    for (my $i = 0; $i < $n; $i++) {
        my $a = $A[$i];
        # Each input number is part of its own range.
        $R[$i]++;
        # Now we assume, that the current input number $A[$i] is
        # the largest element of the range. The minimum lower bound in
        # the input number space is calculated and the previous
        # input number are checked, if the current input number
        # can be added to their ranges.
        my $l = $a * $lu;
        for (my $j = $i - 1; $j >= 0; $j--) {
            last if $A[$j] < $l;
            $R[$j]++;
        }
    }
    # In the worst case, all input numbers are part of the  final
    # output range. Then we would have to look up all smaller input
    # numbers for each input number: O(n^2).
    # In the best case, the final output range is 1, e.g. if the lower
    # bound equals the upper bound. Then the going back is limited to
    # 1 and the complexity is O(n).

    # In the next step the maximum number of a valid range is
    # obtained: O(n)
    my $max = 0;
    for (my $i = 0; $i < $n; $i++) {
        my $a = $R[$i];
        $max = $a if $a > $max;
    }
    print "(Debug) maximal number of elements in a valid range: $max\n";

    # Now each range is checked to find the optimum f
    my $f = 0;
    for (my $i = 0; $i < $n; $i++) {
        # ignore ranges with fewer elements
        next unless $R[$i] == $max;

        # print current range:
        print sprintf "(Debug) A[%d .. %d] = (%g .. %g)\n",
                $i, $i + $max - 1,
                $A[$i], $A[$i + $max - 1];

        # calculate f values based on the smallest/largest element
        my $f_lower = $L / $A[$i];
        my $f_upper = $U / $A[$i + $max - 1];
        # if 1 is in the middle of the f values, then return
        # optimal value
        return 1 if $f_lower <= 1 and $f_upper >= 1;

        # Now $f_lower and $f_upper are both smaller or both greater than 1.
        # A candidate for $f is selected from the current range
        # by using the value that is closer to 1.
        my $f_candidate = $f_lower < 1 ? $f_upper : $f_lower;
        print sprintf "(Debug) f_candidate = %g from (%g .. %g)\n",
                $f_candidate, $f_lower, $f_upper;

        # Compare the candidate with the current f
        if (not $f or abs($f_candidate - 1) < abs($f - 1)) {
            $f = $f_candidate;
        }
    }
    # Complexity is O(n), because the loop body is O(1).

    return $f;
}

my $f = calculate_f(1, 5, [
    0.01, 0.02, 0.5, 1 , 5, 9.5, 9.8, 15, 18, 20, 50, 100
]);

print "(Result) f = $f\n";

__END__

```

The algorithm is explained in the comments. The complexity in the worst case is O(n2), in the best case O(n log n) because of the sorting.

Example output:

```
(Debug) maximal number of elements in a valid range: 6
(Debug) A[4 .. 9] = (5 .. 20)
(Debug) f_candidate = 0.25 from (0.2 .. 0.25)
(Result) f = 0.25

```

# Answer
> 2 votes
# C++

Comments indicate how code works.

```
#include<iostream>
#include<vector>
using namespace std;

int main(){
    // input stores input, sum_values stores the sum of values in the valid range after multiplying
    vector<double>input;
    vector<double>sum_values;

    // stores input, and ends of range
    double num, lower, higher;

    cout<<"Enter the array of values, use 0 to exit: ";

    // input
    while(1){
        cin>>num;
        if(num==0)break;
        input.push_back(num);
    }

    cout<<"Enter the mimimum and maximum values: ";

    cin>>lower>>higher;

    // if array is empty or lower is greater than higher, print 1 and exit
    if(lower>higher||input.size()==0){cout<<"1";return 0;}

    // iterate through all values between .0001 and .9999
    for(double d=.0001;d<1;d+=.0001){

        // check each d for valid ranges
        for(int i=0,valid=0;i<input.size();i++){

            // check if input * d is in valid range
            if(d*input[i]>=lower&&d*input[i]<=higher)valid++;

            // store final number
            if(i==input.size()-1)sum_values.push_back(valid);
        }
    }

    // iterate through compiled sum of ranges and find highest
    int position=0, biggest=-.1;
    for(int i=0;i<sum_values.size();i++){

        // return value closest to 1 for equal values
        if(sum_values[i]>=biggest){
            biggest=sum_values[i];
            position=i;
        }
    }

    // print value
    cout<<(double)position*.0001;

    return 0;
}

```

# Answer
> 2 votes
# Python

```
import collections

def pop_ranges(ranges, max_factor, count, dist, factor):
        """Removes ranges that don't overlap with the next range to be added"""
        while ranges and max_factor < ranges[0][0]:
                cnt = -len(ranges)
                maxf = ranges[-1][1]
                minf = ranges.popleft()[0]
                # Finding the minimum from a constant amount of items (3) is O(1)
                count, dist, factor = min([
                        (count, dist, factor),
                        (cnt, abs(minf - 1), minf),
                        (cnt, abs(maxf - 1), maxf)
                ])
        return count, dist, factor

def scaler(vals, min_val, max_val):
        # Sorting is O(n log n)
        vals.sort()

        factor = dist = count = 0
        # Deque has O(1) operations to the beginning and the end
        ranges = collections.deque()
        # This loop is O(n); the outer loop does n passes and adds one item to
        # ranges on every pass. pop_ranges() contains a loop, but since the loop
        # pops items from ranges, it can only do a total of n passes during the
        # whole outer loop.
        for val in vals:
                # val is growing on every pass, so the factors are shrinking.
                min_factor = min_val / float(val)
                max_factor = max_val / float(val)
                count, dist, factor = pop_ranges(ranges, max_factor, count, dist, factor)
                ranges.append((min_factor, max_factor))
        count, dist, factor = pop_ranges(ranges, ranges[-1][0] - 1, count, dist, factor)

        return factor

print scaler([0.01, 0.02, 0.5, 1 , 5, 9.5, 9.8, 15, 18, 20, 50, 100], 1, 5)

```

This works by sorting the values and keeping track of overlapping factor ranges. New factor ranges are added at the end of the deque and old ranges are removed from the beginning when they no longer overlap with the next range that is about to be inserted. The number of items in the deque corresponds to the number of items on the range and the first and last items give the endpoints of the range. When removing items, the best factor is updated if the current range is better. The complexity should be O(n log n) as explained in the comments.

---
Tags: fastest-algorithm
---


title: Eiffel Tower in 3D

text:
# Question
Title: Eiffel Tower in 3D
This challenge asks you to draw the Eiffel Tower in 3D using different ASCII characters to represent the different sides, similar to this cube:

```
      @@@
   @@@@@@@@@
@@@@@@@@@@@@@@@
x@@@@@@@@@@@@&&
xxx@@@@@@@@&&&&
xxxxx@@@&&&&&&&
xxxxxx&&&&&&&&&
 xxxxx&&&&&&&
   xxx&&&&
     x&&

```

Here is a picture of the Eiffel Tower for you to base your art on:

Your program will input a rotational angle of the side view, then print the Tower as if you were looking at it from that angle. The up/down angle does not need to be accounted for.

Score will be calculated as 1.25\*votes - 0.25\*length as a . Highest score wins.

# Answer
BBC BASIC, 66 chars

Emulator at bbcbasic.co.uk

```
A=PI/6FORJ=0TO83PRINTTAB(9+EXP(J/40)*SIN(A+J*PI/2),J/4);J MOD4:NEXT

```

With white space for clarity:

```
A=PI/6
FOR J=0 TO 83
  PRINT TAB(9+EXP(J/40)*SIN(A+J*PI/2),J/4);J MOD4
NEXT

```

Input is hard coded in radians. Taking user input would add one character, but user would have to input in radians. Removing the MOD4 from the end would still produce a recognisable tower, but might violate the rule regarding character per side.

Basically plots a string of zeros at `exp(J/40)*sin(A)` vs `J/4.` Additional values of the sin are added for the remaining three legs.
> 4 votes

# Answer
# PHP, 364 * 0.25 = 91

Accepts a viewing angle as a query string parameter of the form `?a=0`, `?a=45`, `?a=90`, etc.

```
<pre><?php
$a=45*floor(.5+intval(@$_GET['a'])/45);
$e=array(array(".","|","==","X|","X|","X/","==|","^||","-./","__//","=====","^^-. /","   |__|"),
array(".","|","==","X|","X|","X/","|=|","|^|","|./"," ///",":====",":|-. /","_|  |_|"));
echo "Angle: {$a}°\n\n";
foreach($e[$a&1] as $s){$p=str_pad($s,7);echo strrev($p).substr(strtr($p,'/','\\'),1)."\n";} ?>
</pre>

```

**Examples:**

**a=135**

```
Angle: 135°

      .
      |
     ===
     |X|
     |X|
     /X\
    |=|=|
    |^|^|
    /.|.\
   /// \\\
  ====:====
 / .-|:|-. \
|_|  |_|  |_|

```

**a=200 (rounded to nearest increment = 180°)**

```
Angle: 180°

      .
      |
     ===
     |X|
     |X|
     /X\
    |===|
    ||^||
    /.-.\
   //___\\
  =========
 / .-^^^-. \
|__|     |__|

```

(Yes I know, the angular resolution isn't brilliant. I'll improve on that if I have time.)
> 7 votes

# Answer
# C# - 64 bytes

```
namespace System{class m{static void h(){Console.Write(".");}}}

```

Prints the Eiffel Tower viewed from 500 **26.5** kilometers away. Takes the rotational angle as an argument.

Example usage:

```
eiffel.exe 90

```

# EDIT

I've made an approximation, and it should be about 26.5 kilometers away.

Let's consider the image below, taken from OP and edited to add a "." using the font Monospace 12 without anti-aliasing.

The "." is 2 pixels long and 1 pixels wide whereas the tower is 400 pixels long and 663 pixels wide(approximately).

Let's assume the tower is viewed from 100 meters away.

If we want to make it look like a 2x1 box, we would need to make it (again, approximately) 265.5 times smaller(200 times smaller for the height and 531 times smaller for the width).

If we multiply 265.5 with 100 meters, we get 26550 meters, which is 26.5 kilometers.
> 1 votes

---
Tags: ascii-art, code-challenge, popularity-contest
---


title: Generate code in another language

text:
# Question
Title: Generate code in another language
Write a program in language A which outputs a program in language B where:

1. Language A != Language B
2. The output is itself a solution to this question.

This is a popularity contest. If you want to define your own BNFs/grammars for this, feel free, but try not to make it too boring by doing so.

EDIT: The more languages it ends up generating code in, the better (in my opinion).

EDIT2: Try to use languages that are not similar (I.e. generate the code in a different family of languages). (E.g. C to Scheme)

# Answer
> 2 votes
# php --\> asp --\> html --\> xhtml .......

```
 Hello

```

Infinite languages

# Answer
> -2 votes
## HQ9+, HQ9++ (and more)

```
Q

```

I'm starting to like this family of languages.

---
Tags: popularity-contest, code-generation
---


# Question
Title: How large can you make this function without adding any lines of code that do nothing
```
    public int UndocumentedCode(int a, int b)
    {
        while (true)
        {
            a -= b;
            b += a;
            a = b - a;
            if (b < a)
            {
                return b;
            }
            else
            {
                b += 1;
            }
        }
    }

```

First figure out what it does (or look at the spoiler) the challenge is to make it as long as possible without adding lines that do absolutely nothing e.g. if (true) or do anything completely meaningless e.g. a declaration that isn't used/needed.

any lines of code that can be removed, with the result still being the same, do not count

the more confusing looking, the better.

> it is a function for getting the lesser of two numbers. the if (b \< a) return b is self explanatory. The a and b calculations at the top are to swap b and a around, so when it loops it will check a \< b. the b+=1 is to prevent infinite loops if they are the same

# Answer
> 5 votes
Not sure this is quite in the spirit of things, and I'm not going to write *all* the code, but technically all of the lines in the following would be necessary for the function to work. Note, for the sake of brevity I've changed the types to `char`, which I will assume is an 8-bit signed type (I didn't spot any mention of a specific language):

```
public char UndocumentedCode(char a, char b)
{
    if (a == -128 && b == -128)
        return -128;
    if (a == -127 && b == -128)
        return -128;
    if (a == -126 && b == -128)
        return -128;
    ...
    // can you see where I'm going with this?
    ...
    if (a == -128 && b == -127)
        return -128;
    if (a == -127 && b == -127)
        return -127;
    if (a == -126 && b == -127)
        return -127;
    ...
    // yawn...
    ...
    if (a == 125 && b == 127)
        return 125;
    if (a == 126 && b == 127)
        return 126;
    if (a == 127 && b == 127)
        return 127;

    // i think you get the idea by now
}

```

The code would of course be platform dependant, and cases would need to be written for all combinations of negative and positive numbers. Perhaps some kind of script to write the file, to save aching fingers, and to automatically generate the code based on platform-specific options.

If we just went with 8-bit ints, then the final code would be roughly 131075 lines long, with all lines being necessary to cover all possibilities.

# Answer
> 0 votes
```
 public int UndocumentedCode(int a, int b)
 {
   while (true)
   {
       a -= b;
       b += a;
       a = b - a;
       bool isGT? = b < a;
       if isGT?
       {
          return b;
       }
       else
       {
         b += 1;
       }
    }
}

```

Add another statement with boolean condition.

# Answer
> 0 votes
```
public int UndocumentedCode(int a, int b)
{
    int a1 = a;
    int a2 = a1;
    int a3 = a2;
    int a4 = a3;
    int a5 = a4;
    int a6 = a5;
    int a7 = a6;
    int a8 = a7;
    int a9 = a8;

    // etc

    int a9999 = a9998
    int c = a9999;
    while (true)
    {
        c -= b;
        b += c;
        c = b - c;
        if (b < c)
        {
            return b;
        }
        else
        {
            b += 1;
        }
    }
}

```

---
Tags: popularity-contest, code-bowling
---


title: Build an ice puzzle generator + solver

text:
# Question
Title: Build an ice puzzle generator + solver
In Twitch Plays Pokémon, one of the most annoying obstacles one can face is an ice puzzle, where you must travel from one place to another by sliding all the way in one direction until you either hit a wall or a boulder.

Your task is to build a program that will generate a random difficult ice puzzle.

Your program will accept three numbers, `M`, `N`, and `P`, as input (with `10 <= M <= 30`, `15 <= N <= 40`, and `0 <= P < 65536`):

```
12 18

```

and will output:

* An `M` by `N` grid consisting of `.` and `O`, representing ice and a boulder respectively.
* A position marker representing where the puzzle is entered from. This position marker consists of a letter `L`, `R`, `T`, or `B`, representing left, right, top, and bottom, followed by a number representing the position (from the left or top) on that side to be entered from.
* A similar position marker representing where the puzzle is exited out of.
* **The shortest solution to the puzzle, consisting of a sequence of `L`, `R`, `U`, and `D` respectively.**

Example output:

```
..O...O...........
............O.....
..O...............
.......O..........
..................
...........O......
O..O...........O..
..........O.......
..O..........O....
........O.........
O....O.........O..
............O.....
R 4
B 5
LDLDRULD
(Note that this output is actually invalid because it is not actually long enough.)

```

For an input `M` and `N`, the solution to the puzzle must have at least `min(M, N)` steps and move at least `2 (M + N)` total spaces. (For reference, the above puzzle moves a total of 12 steps, moving 69 spaces.) Your puzzle generator must generate a different `M` by `N` puzzle with a different solution path (i.e. a different sequence of steps for each solution) for each seed `P`.

* Note that the requirement of a different solution path is to avoid solutions that try to systematically generate rock paths, like Claudiu's solution here. If there are two or three pairs of identical solutions due to quirks in randomness, that will be okay, as long as the program is not *intentionally* trying to systematically generate puzzles with the same sequence of moves.

The shortest code to do the above wins.

# Answer
# Python, ~~672~~ 548 characters, more interesting puzzles

Although going strictly by the rules, my other Python program beats this one, I decided to write one that would generate more interesting puzzles anyway. Here it is:

```
R=range;import random as J;X=J.randint
x=(0,1,-1,0);y=x[2:]+x
g=lambda r,c:(0<=r<H)+(0<=c<W)>1and f[r][c]or x[(r,c)in(A,E)]
l=lambda r,c:g(r+y[d],c+x[d])<1and(r,c)or l(r+y[d],c+x[d])
H,W,P=input();J.seed(P)
while 1:
 A=(-1,X(0,W));E=(H,X(0,W));f=[[X(0,7)for _ in R(W)]for _ in R(H)]
 q=[(A,'')];n=z={}
 while q and n!=E:
    n,O=q.pop()
    for d in R(4):
     N=l(*n)
     if g(n[0]+y[d],n[1]+x[d])and N not in z:q[:0]=[(N,O+"URLD"[d])];z[N]=1
 if(n==E)*len(O)>min(H,W):print"\n".join(''.join('O.'[c>0]for c in T)for T in f),"\nT",A[1],"\nB",E[1],"\n",O;break

```

Indentation levels are space, tab, tab+space.

**Samples**:

```
$ echo [10,15,0] | python ice2.py
.....OO........
...............
...O....O.OO..O
...........O...
..O....O.......
.......O....O..
....O..........
.............O.
..............O
...............
T 1
B 10
DLURDRURULDRD

```

It uses `P` as a seed, so each `P` will generate the same puzzle, and each different `P` is exceedingly likely to be different:

```
$ echo [10,15,1] | python ice2.py
.OOO.O.........
...O......O.O.O
.......O.......
..O..........OO
.....O.........
.............O.
.O.............
.O............O
O....O.........
......O........
T 14
B 8
DLDRDLURULD

```

It works reasonably fast up to sizes of `M=25,N=40` but past that it gets really slow. It should theoretically work for `M=30, N=40` if you let it run long enough. I've manually written in the trail here since it is hard to follow - the program just outputs the puzzle.

```
$ echo [25,40,0] | python ice2.py
                   *
...................dO....urrrO..O..O....
....O.....O........dO....u..dO..........
..........O.....O..d....Ou.Odrrrrrrrrrrr
...........O.......d.O..Ou..O.....OOllld
.O....O.OO.........drrrrrrO....Olllud..O
O......O...O.O.....O............dO.ud...
O........OO..........O.........Od..ud..O
.........O......................d..ud...
....O.....O.O....O.....O........d..ud.O.
.....O..O...................O...d..udO..
.........O.........O..O.........d..ud...
.......O.O...O..O.OO....O...OOlldOOld...
........Olllllllllu....OO.OO..dOO...O...
.O.O....Od........u......O....d..O...O..
..O....O.d........u..O........d..O..O...
....O....d..O.....uO.....O....d.........
.........d........u...........d.........
.........d....O...u.O..O.....Od.O.......
........Od...O....u...........d.........
.O.....OuxrrrrO...u...OOOO..O.d.........
........udO..dO.O.u...........d.........
O..O.O..ud...d..urrO..........d.O...O...
........ud...d..u.O.O........Od..O...O..
..OO....ud..Od..u......OllllludO.....O..
..O....OldO..dOOlllllllld...Old...O..O..
             *
T 19
B 13
DRURDRDLDLULDLDLULDLURULDLURD

```

**Explanation**:

The program loops, generating a random start position on the top, a random end position on the bottom, and a random grid with a `12.5%` chance for a boulder on any given spot. It then solves the puzzle with a breadth-first-search and if the solution exists and is bigger than `min(H,W)`, it prints and exits.
> 6 votes

# Answer
# Python, ~~235~~ ~~206~~ ~~185~~ 176 characters

```
H,W,P=input()
t=''
for x in range(16):t+=".O"[(P>>x)%2]
for n in[t[1:],t[0],"O","...O"]+["."]*(H-5)+[".O.."]:print(n*W)[:W]
print"B 1\nR",(H,3)[-W%4/2],"\n",("URDR"*W)[:W+W%2]

```

**Usage**:

Input is through stdin of the form `[M, N, P]`.

```
$ echo [14, 17, 2] | python ice.py
O..............O.
.................
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR

```

You said the maps had to be different for each seed `P`... and they are:

```
$ echo [14, 17, 233] | python ice.py
..O.OOO..........
OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR
$ echo [14, 17, 65133] | python ice.py
.OO.OO..OOOOOOO.O
OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOOO
...O...O...O...O.
.................
.................
.................
.................
.................
.................
.................
.................
.................
.O...O...O...O...
B 1
R 3
URDRURDRURDRURDRUR

```

And an example w/ a different size:

```
$ echo [10, 15, 65133] | python ice.py
.OO.OO..OOOOOOO
OOOOOOOOOOOOOOO
OOOOOOOOOOOOOOO
...O...O...O...
...............
...............
...............
...............
...............
.O...O...O...O.
B 1
R 10
URDRURDRURDRURDR

```

Satisfies all the supplied objective criteria:

* Each `P` leads to a different puzzle
* There is only one solution, thus it is the shortest
* The solution takes `N + N%2` steps, which is at least `N`
* The solution always takes more than `2 (M + N)` total spaces

---

**Explanation**:

Each row is constructed by repeating a certain string element `W` times and limiting the length to `W` (I use `H` and `W` instead of `M` and `N`).

The first two rows depend on `P` to make each puzzle unique. Basically, note that `P` fits into a 16-bit unsigned integer. I convert `P` to binary, using `.` for 0 and `O` for 1:

```
t=''
for x in range(16):t+=".O"[(P>>x)%2]

```

The first row element is the last 15 bits, `t[1:]`, while the second row element is the 1st bit, `t[0]`. I couldn't put it all on one row because the minimum width is 15, which wouldn't fit all 16 bits if `P` \> 32767. Thus the first two rows uniquely represent each of the possible values of `P`.

The third row is a full wall so that the value of `P` doesn't affect the solution.

Then follow the actual maze elements. This line prints them all, repeating them up to the cap. The result is as you see above:

```
for n in[t[1:],t[0],"O","O..."]+["."]*(H-5)+["..O."]:print(n*W)[:W]

```

The rest was just figuring out how to solve the dynamically generated maze. This depends only on the width of the maze. I noted that the solutions, for a given width, were:

```
  W  | solution
-----+---------
  1  | UR
  2  | UR
  3  | UR DR
  4  | UR DR
  5  | UR DR UR
  6  | UR DR UR
  7  | UR DR UR DR
  8  | UR DR UR DR

```

etc. Hence it's just `URDR` repeated and cut off at the right place, `W+W%2`.

```
print"B 1\nR",(H,3,3,H)[W%4],"\n",("URDR"*W)[:W+W%2]

```
> 5 votes

# Answer
## Java - 2632

While I admire the technical purity of Claudiu's answer, I decided to try my hand at making *slightly* more difficult puzzles ;)

**Basic steps (pretty simple):**

```
Randomize entry location
Step forward
For min(m,n)-1 steps:
    Rotate left or right
    Slide until I hit something or go a random distance
    Place a rock in front of stopping location
If I can slide straight to any wall:
    Slide to exit
Else
    Create another step and try again

If at any step I get trapped, start over
If BFS finds shorter path, start over

```

I also mark each spot as 'nogo' as I'm sliding. If I end up on a nogo spot(or right in front of one which would mean a rock was going there), it's an invalid step.

So, basically the idea is to randomly generate a *lot* of maps, and keep the first one that is valid. I plan to make this smarter(backtracking, etc), but it works fine right now. It might also cut down on some redundant code, we'll see.

As it is, it generates small maps(15x10) almost instantly, medium(30x20) maps in a couple seconds, and large(40x30) in some random amount of time between 20 seconds and 20 minutes, depending on seed. It tests between 300k-500k maps/second on my machine, depending on size.

Side note: Sometimes the maps aren't *too* hard, simply because there are only as many rocks as steps, and unless the step takes you to a wall, most times there's only one option if you want to hit an actual rock. I'll fix that later by placing "random" rocks in safe spots after all the steps are drawn. Since nogo spots are already marked, that should be pretty simple. For now, just enjoy these examples:

**Output showing different sizes/seeds:**

```
$ java I 30 20 6851              $ java I 15 10 1     $ java I 15 10 65513

............................O.      .......O.......     ....O..........
..............................      ...............     ...............
..............................      .........O.....     .........O.....
..........O......O............      .............O.     ..............O
...............O...........O..      ...............     ...............
..............................      .......O.......     .....O.O.......
..............................      O..............     ...............
........................O.....      ...............     ..........O....
..............................      ...............     O..............
...O.......................O..      ......O........     ...............
O...............O.OO..........
..............O..........O....
...........O..................      T 14                R 6
....O.........................      T 7                 T 14
..............................      DLDLULURU           LULDLDRURU
..............................
..............................
.................O............
.O............................
..............................

B 28
R 9
ULURDLDLDRURDLDRURUR

```

**Max size 40x30:**

```
$ java I 40 30 2

........................................
........................................
........................................
........................................
................O.......................
..........O.............................
........................................
.......O................................
.....................O..........O.......
......................O.................
.................................O......
......................................O.
........................................
........................................
..............................O.........
...........O............................
........................................
.......................................O
.........O...................O..........
....................O...................
...............................O........
............O..O......................O.
......O...........O.....................
..................O....O................
..................................O.....
........................................
..............................O.........
.....................................O..
...........O............................
...................O....................

B 19
B 11
URURDLULULDRDRDLULDLDLULURDLD

```

**Golfed:**

```
import java.util.*;import java.awt.*;class I{int m,n,p,g,a[][],b[][];Random r;Point s,e,c;ArrayList<Integer>z;void Q(String q,int l){if(l>0)System.out.println(q);else System.out.print(q);}void G(String[]y){m=Integer.valueOf(y[0]);n=Integer.valueOf(y[1]);p=Integer.valueOf(y[2]);r=new Random(p);Q("",1);int o=0,i,j,u=0;char t,f[]={85,76,68,82};while(o<3){if(++u%20000==0)Q("\r#"+u,0);a=new int[m+2][n+2];b=new int[m+2][n+2];for(i=0;i<m+2;i++)for(j=0;j<n+2;j++)if(i==0||i==m+1||j==0||j==n+1)a[i][j]=2;s=new Point();int e=r.nextInt(m*2+n*2);if(e<m*2){s.x=e%m+1;s.y=e<m?0:n+1;}else{s.y=(e-m*2)%n+1;s.x=(e-m*2)<n?0:m+1;}if(s.x<1)g=3;else if(s.x>m)g=1;else if(s.y<1)g=2;else if(s.y>n)g=0;a[s.x][s.y]=0;c=new Point(s);z=new ArrayList<Integer>();z.add(g);for(i=0;i++<Math.min(m,n)-1;)if(N()<1&&N()<1)break;o=((z.size()>=Math.min(m,n)-1)?1:0)+F()+((V()==z.size())?1:0);}Q("\r",0);for(j=1;j<n+1;j++){for(i=1;i<m+1;i++)Q(String.valueOf(a[i][j]>0?'O':'.'),0);Q("",1);}Q("\n\n",0);if(s.x<1||s.x>m){t=s.x<1?'L':'R';u=s.y;}else{t=s.y<1?'T':'B';u=s.x;}Q(t+" "+u,1);if(e.x<1||e.x>m){t=e.x<1?'L':'R';u=e.y;}else{t=e.y<1?'T':'B';u=e.x;}Q(t+" "+u,1);for(i=0;i<z.size();)Q(String.valueOf(f[z.get(i++)]),0);Q("",1);}public static void main(String[]a){new I().G(a);}int F(){int c=0;while(C()<1&&c++<10)if(N()<1)return 0;return e==null?0:1;}int C(){int d=g<2?-1:1;if(g%2<1){int y=c.y;while(y>0&&y<n+1){y+=d;if(a[c.x][y]==1)return 0;}e=new Point(c.x,y);}else{int x=c.x;while(x>0&&x<m+1){x+=d;if(a[x][c.y]==1)return 0;}e=new Point(x,c.y);}a[e.x][e.y]=0;return 1;}int V(){if((s.x-e.x)+(s.y-e.y)<2)return 0;Queue<Point>q=new ArrayDeque<Point>();Queue<Integer>d=new ArrayDeque<Integer>();a[s.x][s.y]=-2;q.add(s);d.add(0);while(q.size()>0){Point t=q.poll();int h=d.poll(),i=0;if(t.equals(e))return h;for(;i<4;i++){Point n=S(a,t,i<2?0:1,i%2<1?-1:1,99,1);if(a[n.x][n.y]==-2)continue;a[n.x][n.y]=-2;q.add(n);d.add(h+1);}}return 0;}int N(){Point q;int d=g<2?-1:1,x,y;System.arraycopy(a,0,b,0,a.length);q=S(b,c,g,d,r.nextInt((g%2<1?n:m)/2)+2,0);if(q.x<1||q.y<1||q.x>m||q.y>n||q.equals(c)||b[q.x][q.y]!=0)return 0;x=q.x;y=q.y;if(g%2<1)y+=d;else x+=d;if(b[x][y]<0)return 0;b[q.x][q.y]=-1;b[x][y]=1;int f=r.nextInt(2)<1?-1:1;g=g%2<1?(f<0?1:3):(g=f<0?0:2);c=q;System.arraycopy(b,0,a,0,a.length);z.add(g);return 1;}Point S(int[][]u,Point f,int w,int d,int q,int s){int i=1,x=f.x,y=f.y;for(;i<=q;i++){if(w%2<1)y=f.y+i*d;else x=f.x+i*d;if(e!=null&&e.x==x&&e.y==y)return e;if(y<0||y>n+1||x<0||x>m+1)return f;if(s<1&&u[x][y]<1)u[x][y]=-1;if(u[x][y]>0){if(w%2<1)y-=d;else x-=d;return new Point(x,y);}}if(w%2<1)return new Point(f.x,f.y+i*d);else return new Point(f.x+i*d,f.y);}}

```

**With line breaks:**

```
import java.util.*;
import java.awt.*;

class I{
    int m,n,p,g,a[][],b[][];
    Random r;
    Point s,e,c;
    ArrayList<Integer>z;

    void Q(String q,int l){if(l>0)System.out.println(q);else System.out.print(q);}

    void G(String[]y){
        m=Integer.valueOf(y[0]);
        n=Integer.valueOf(y[1]);
        p=Integer.valueOf(y[2]);
        r=new Random(p);
        Q("",1);

        int o=0,i,j,u=0;
        char t,f[]={85,76,68,82};
        while(o<3){
            if(++u%20000==0)
                Q("\r#"+u,0);

            a=new int[m+2][n+2];
            b=new int[m+2][n+2];
            for(i=0;i<m+2;i++)
                for(j=0;j<n+2;j++)
                    if(i==0||i==m+1||j==0||j==n+1)
                        a[i][j]=2;

            s=new Point();
            int e=r.nextInt(m*2+n*2);
            if(e<m*2){
                s.x=e%m+1;
                s.y=e<m?0:n+1;
            }else{
                s.y=(e-m*2)%n+1;
                s.x=(e-m*2)<n?0:m+1;
            }
            if(s.x<1)g=3;
            else if(s.x>m)g=1;
            else if(s.y<1)g=2;
            else if(s.y>n)g=0;

            a[s.x][s.y]=0;
            c=new Point(s);
            z=new ArrayList<Integer>();
            z.add(g);

            for(i=0;i++<Math.min(m,n)-1;)
                if(N()<1&&N()<1)
                        break;
            o=((z.size()>=Math.min(m,n)-1)?1:0)+F()+((V()==z.size())?1:0);
        }

        Q("\r",0);
        for(j=1;j<n+1;j++){
            for(i=1;i<m+1;i++)
                Q(String.valueOf(a[i][j]>0?'O':'.'),0);
            Q("",1);
        }
        Q("\n\n",0);
        if(s.x<1||s.x>m){
            t=s.x<1?'L':'R';
            u=s.y;
        }else{
            t=s.y<1?'T':'B';
            u=s.x;
        }
        Q(t+" "+u,1);
        if(e.x<1||e.x>m){
            t=e.x<1?'L':'R';
            u=e.y;
        } else {
            t=e.y<1?'T':'B';
            u=e.x;
        }
        Q(t+" "+u,1);
        for(i=0;i<z.size();)
            Q(String.valueOf(f[z.get(i++)]),0);
        Q("",1);
    }

    public static void main(String[]a){
        new I().G(a);
    }

    int F(){
        int c=0;
        while(C()<1&&c++<10)
            if(N()<1)
                return 0;
        return e==null?0:1;
    }

    int C(){
        int d=g<2?-1:1;
        if(g%2<1){
            int y=c.y;
            while(y>0&&y<n+1){
                y+=d;
                if(a[c.x][y]==1)
                    return 0;
            }
            e=new Point(c.x,y);
        }else{
            int x=c.x;
            while(x>0&&x<m+1){
                x+=d;
                if(a[x][c.y]==1)
                    return 0;
            }
            e=new Point(x,c.y);
        }
        a[e.x][e.y]=0;
        return 1;
    }

    int V(){
        if((s.x-e.x)+(s.y-e.y)<2)
            return 0;
        Queue<Point>q=new ArrayDeque<Point>();
        Queue<Integer>d=new ArrayDeque<Integer>();
        a[s.x][s.y]=-2;

        q.add(s);
        d.add(0);
        while(q.size()>0){
            Point t=q.poll();
            int h=d.poll(),i=0;
            if(t.equals(e))
                return h;
            for(;i<4;i++){
                Point n=S(a,t,i<2?0:1,i%2<1?-1:1,99,1);
                if(a[n.x][n.y]==-2)
                    continue;
                a[n.x][n.y]=-2;
                q.add(n);d.add(h+1);
            }
        }
        return 0;
    }

    int N(){
        Point q;
        int d=g<2?-1:1,x,y;
        System.arraycopy(a,0,b,0,a.length);
        q=S(b,c,g,d,r.nextInt((g%2<1?n:m)/2)+2,0);
        if(q.x<1||q.y<1||q.x>m||q.y>n||q.equals(c)||b[q.x][q.y]!=0)
            return 0;
        x=q.x;
        y=q.y;
        if(g%2<1)
            y+=d;
        else
            x+=d;
        if(b[x][y]<0)
            return 0;
        b[q.x][q.y]=-1;
        b[x][y]=1;
        int f=r.nextInt(2)<1?-1:1;
        g=g%2<1?(f<0?1:3):(g=f<0?0:2);
        c=q;
        System.arraycopy(b,0,a,0,a.length);
        z.add(g);
        return 1;
    }

    Point S(int[][]u,Point f,int w,int d,int q,int s){
        int i=1,x=f.x,y=f.y;
        for(;i<=q;i++){
            if(w%2<1)
                y=f.y+i*d;
            else
                x=f.x+i*d;
            if(e!=null&&e.x==x&&e.y==y)
                return e;
            if(y<0||y>n+1||x<0||x>m+1)
                return f;
            if(s<1&&u[x][y]<1)
                u[x][y]=-1;
            if(u[x][y]>0){
                if(w%2<1)
                    y-=d;
                else
                    x-=d;
                return new Point(x,y);
            }
        }
        if(w%2<1)
            return new Point(f.x,f.y+i*d);
        else
            return new Point(f.x+i*d,f.y);
    }
}

```
> 4 votes

---
Tags: code-golf
---


# Question
Title: Floating point addition, without floats!
Your task is to write a program, in any language, that adds two floating point numbers together WITHOUT using *any* fractional or floating point maths. Integer maths is allowed.

**Format**

The format for the numbers are strings containing 1's and 0's which represent the binary value of a IEEE 754 32-bit float. For example the number 2.54 would be represented by the string "01000000001000101000111101011100".

**Goal**

You program should input two numbers in the above mentioned format, add them together, and output the result in the same format. The shortest answer in any language wins!

**Rules**

Absolutly no floating point, decimal, or any kind of non-integer maths functions are allowed.

You can assume that the input is clean (i.e. contains only 1's and 0's).

You can assume that the inputs are numbers, and not Inf, -Inf, or NaN or subnormal. However, if the result is greater than the max value or smaller than the min value, you should return Inf and -Inf respectively. A subnormal (denormal) result may be flushed to 0.

You do not have to handle rounding properly. Don't worry if your results are a few bits out.

**Tests**

To test your programs, you can convert between decimal and floating point binary numbers using this tool.

1000 + 0.5 = 1000.5

```
01000100011110100000000000000000 + 00111111000000000000000000000000 = 01000100011110100010000000000000

```

float.MaxValue + float.MaxValue = Infinity

```
01111111011111111111111111111111 + 01111111011111111111111111111111 = 01111111100000000000000000000000

```

321.123 + -123.321 = 197.802

```
01000011101000001000111110111110 + 11000010111101101010010001011010= 01000011010001011100110101010000

```

Good luck!

# Answer
> 3 votes
## Python, 224 chars

This code converts a floating point input `f` to the integer `f*2^150`, does the addition using python native big integers, then converts back.

```
V=lambda x:((-1)**int(x[0])<<int(x[1:9],2))*int('1'+x[9:],2)
B=lambda x,n:B(x/2,n-1)+'01'[x&1]if n else''
def A(x,y):
 v=V(x)+V(y)
 s=e=0
 if v<0:s=1;v=-v
 while v>=1<<24:v/=2;e+=1
 if e>254:v=0
 return'%d'%s+B(e,8)+B(v,23)

```

# Answer
> 3 votes
# J (172 characters)

Since IEEE 754 allows five rounding rules, I chose the "toward 0" rule. Here is my code:

```
b=:(_1&^)@".@{.*[:#.1x,("."0)@(9&}.),#.@:("."0)@}.@(9&{.)$0:
a=:b@[([:,(<&0)":"0@:,,@((8$2)&#:)@(-&24)@$@#:,}.@(24&{.)@#:@|)@(]`(**2x^278"_)@.((>&((2x^278)-2x^254))@|))@+b@]

```

The very same examples you give (but not exactly the same results because of the different rounding rule):

```
   '01000100011110100000000000000000' a '00111111000000000000000000000000'
01000100011110100010000000000000
   '01111111011111111111111111111111' a '01111111011111111111111111111111'
01111111100000000000000000000000
   '01000011101000001000111110111110' a '11000010111101101010010001011010'
01000011010001011100110101001111

```

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


# Question
Title: Shortest Program to Solve a Quartic Equation
Write the shortest program to solve a quartic equation.

A quartic equation is a polynomial equation of the form:

\\$ax^4 + bx^3 + cx^2 + dx + e=0\\$

A solution for \\$x\\$ is a number such that the above evaluates to 0.

---

**Rules**

* The program must take in the 5 floating point coefficients of the equation \\$ax^4+bx^3+cx^2+dx+e\\$ as `"a b c d e"` separated by spaces.
* It must then output a single real solution. If there exist no real solutions then it outputs an `"n"`.
* No bonus for extra solutions.
* No use of CAS (Computer algebra systems). This includes symbolic manipulation properties of Mathematica and related software.
* No connecting to external libraries, web calculators etc...
* You may use formulas or your own manipulation
* Native math libraries that do not solve equations may be used, eg. .NET: System.Math
* You may deduct 50 from your char count if recursion is a main technique used.
* As long as there is no difference with the answer obtained algebraically, numerical approximation is welcome however adds 25 chars to your solution. This really relies on the accuracy of the floating-point numbers. (Which should be 64 bit).

The winner will be picked in 1 week. (26/02/2014)

# Answer
# C++ A fast and robust solution, 704 chars + numeric - recursion = 679

```
#include "stdafx.h"
#include "math.h"
double a,b,c,e,j,k,l,p,q,t,z;void s(double x, int i){if(i==99)printf("%f\n",x);else s(x-((x+b)*x*x*x+c*x*x+l*x+e)/(4*x*x*x+j*x*x + k*x + l),i+1);}
void _tmain(){double r[8];scanf_s("%lf%lf%lf%lf%lf",&a,&b,&c,&l,&e);b/=a;c/=a;l/=a;e/= a;j=3*b;k=2*c;p=(12*k-j*j)/48;q=(2*j*j*j-36*j*k+432*l)/1728;z=q*q/4+p*p*p/27;int u=0,v=0,g;
for(g=1;g<4;g++){r[g]=z>0|p==0?cbrt(-q/2+sqrt(z))+cbrt(-q/2-sqrt(z))-j/12:sqrt(-p/.75)*cos(acos(-q/sqrt(-p*p*p*4/27))/3-g*acos(-.5))-j/12;r[g+4]=(r[g]+b)*pow(r[g],3)+c*r[g]*r[g]+l*r[g]+e;if(r[g+4]>r[g+3]|g==1)u=g;if(r[g + 4]<r[g+3]|g==1)v=g;}
if(r[v+4]>0)printf("n\n");if(r[v+4]==0)printf("%f\n",r[v]);if(r[v+4]<0)s(2*r[v]-r[u]+(r[v]-r[u]==0),0);}

```

This is by no means the shortest answer, but so far no other answer has confirmed that it will work with curves with the full 3 stationary points (maxima/minima.) These correspond to curves with large values of b and c of opposite sign to a. None of the test data in the other solutions has local maxima/minima apart from the global one. The nearest is Eelvex's `1 2 0 0 1` which has a kink on one side where dy/dx falls to zero.

This program handles all the test data shown in other solutions, plus the following interesting examples, amongst others:

```
1 0 1 0 0 --> multiple root 0
1 0 -1 0 0 --> multiple root at 0, but the program prefers the simple root at -1
1 0 -1 0 0.25 -->  multiple roots at +/- 0.7071 = sqrt(0.5)

```

It cannot handle the case a=0, but that is not a quartic so it is out of scope.  ~~The only problem I have found but not eliminated is b=c=d=0, but that is an easy problem to fix. I will do it when I golf the code (if I get round to that.) I expect it to come in around 700-800 chars.~~

**How it works**

The program divides the whole formula by `a` (which does not affect the roots, but ensures that we know that `y= +infinity` at `x = +/- infinity` )

It then calculates the formula for dy/dx (a cubic) and solves this analytically for dy/dx=0. The code to do this is quite short (the explanation in the comments is much longer than the code itself.)

It calculates the values of `y` at the up to 3 stationary points where dy/dx=0 and looks for the lowest (global minimum.) If this `y` is positive here , the whole curve is above the x axis and there are no roots.

If `y` is zero, then it is a root and this is reported directly. Such a root would be problematic for newton raphson.

If `y` is less than zero, the program makes a guess for the root on the opposite side of the global minimum from the other stationary points (to avoid getting trapped in the local maximum if there is one.)

Then it searches using newton-raphson (recursive, as you insisted.) This method is fast and simple, and once the right region of the curve has been identified, does not run the risk of dividing by zero.

I did run into other problems with it though. It quickly got very close to a solution (good enough for a human) but kept searching. With the rapid initial convergence, I assumed that the problem was that it couldn't get to f(x)==0 because f'(x) was large and f(x)/f'(x) was being rounded to zero in the calculation. So I put in an extra test condition for f(x)/f'(x) but it still did the same. Then I limited it to just 10 iterations, which is more than enough for all the tests I have done.

The current version goes up to 99 iterations. The ungolfed version has medium verbosity output (with uncommentable code for high verbosity) as seen in the screenshot and has its iterations terminated when f(x)==0. The golfed version has low verbosity (in accordance with specified requirements) and always runs to 99 iterations. The golfed version has other minor differences, such as no while loop and simplified (but less clear) expressions.

There are certainly other methods which might work better, but I think that might go into another answer (which I don't think I have time for.)

**Ungolfed version**

```
#include "stdafx.h"
#include "math.h"

double a,b,c,d,e,j,k,l,p,q,t,z;
//explanation of variables
//dy/dx= i* x3 + j*x2 + k*x + l. No i variable needed as it is normalised to 4.
//depressed form of dy/dx: t3+pt+q. A subsitution is used to eliminate the squared term, see below.
//z=q2/4 + p3/27. z is proportional to the "discriminant." The sign tells the number of roots of dy/dx
// +ve z means 1 real root, -ve z means 3 real roots, 0 means one simple root plus a double root.

// recursive newton-raphson to depth i
void s(double x, int i){
    double m=(x + b)*x*x*x + c*x*x + d*x + e;
    if (m == 0 | i == 99)  printf("z= %f x= %f y= %f iteration %d\n", z,x,m,i);
    else s(x-m/(4*x*x*x + j*x*x + k*x + l), i+1);

}

void _tmain(){
    while (true){

        double r[8];
        //r[1,2,3] and r[5,6,7] store x and y values of the maxima and minima.
        //r[0] and r[4] are dummies to handle [subscript-1] references.

        scanf_s("%lf %lf %lf %lf %lf", &a, &b, &c, &d, &e);
        //uncomment for verbose output: printf("data for minima and maxima \n");
        //uncomment for verbose output: printf("   z       x       dy/x      y     hi/low \n");
        //hi/low indicate which y values are highest and lowest: 1st, 2nd, 3rd.

        //Divide by a to give a "monic polynomial" with a=1.
        //This does not affect the roots but saves a lot of typing of powers of a.
        // differentiate to i*x3 + j*x2 + k*x + l. As a=1, we know i=4.
        b /= a; c /= a; d /= a; e /= a;
        j = 3*b; k = 2*c; l = d;

        // to prepare to solve this cubic, convert to depressed cubic t3+pt+q, eliminating x2. x=t-j/(3*i)
        // p=(3*i*k - j2)/(3*i2) q=(2*j3 - 9*i*j*k + 27*i2*l)/27*i3. But we know i=4.
        p = (12 * k - j*j) / 48;
        q = (2 * j*j*j - 36 * j*k + 432 * l) / 1728;
        z = q*q / 4 + p*p*p / 27;

        //u and v indicate which of the stationary points are highest and lowest.
        //solve dy/dx, store the roots in r[1,2,3] and the y values in r[5,6,7].
        int u=0,v=0,g;
        for (g = 1; g < 4; g++){

            //if z>0 or p==0 use cardano's method to store the one real root of dy/x three times in r[1,2,3]
            //if z<=0 use viete's trigonometric method to find the multiple real roots.
            //use of different methods for each case avoids the need to handle complex numbers.

            r[g] =z > 0 | p==0? cbrt(-q / 2 + sqrt(z)) + cbrt(-q / 2 - sqrt(z)) - j / 12 :
                sqrt(-p / .75)*cos(acos(-q / sqrt(-p * p * p * 4 / 27)) / 3 - g*acos(-.5)) - j / 12;

            r[g+4] = (r[g]+b)*pow(r[g],3) + c*r[g]*r[g] + d*r[g] + e;

            if (r[g + 4]>r[g+3]|g==1)u=g;
            if (r[g + 4]<r[g+3]|g==1)v=g;

            // uncomment for verbose output
            //printf("%f %f %f %f %d %d \n  \n", z, r[g], 4 * pow(r[g], 3) + j*pow(r[g], 2) + k*r[g] + l, r[g+4], u, v);
        }

        //because we divided by a, the new a=1 and y tends to infinity at large |x|.
        //so if the lowest stationary point has y>0, the whole curve is above the x axis and there is no solution.

        //if the lowest stationary point has y=0 it is tangent to the x axis and would cause problems for newton-raphson

        //if the lowest stationary point has y<0, use newton raphson, 99 iterations. ensure 1st guess is on the side
        //opposite the highest stationary point, just in case that point also has y<0, to avoid getting trapped.
        //special case: if r[v]-r[u] == 0 (implies only one stationary point) then add 1!

        if (r[v+4] >0) printf("n\n");
        if (r[v+4]==0) printf("z= %f x= %f multiple root", z,r[v]);
        if (r[v+4] <0) s(r[v]+(r[v]-r[u])+(r[v]-r[u]==0),0);
    }
}

```

**Output**

All data tested by other answers is here, as well as many additional examples. The sign of the value `z` is positive when there is only one stationary point where dy/dx=0, negative when there are three (2 minima and a maximum if a is positive), and zero when there are two (a minimum if a is positive, plus an inflexion.) This is the only answer so far that presents test cases for three stationary points.

The `y` values are shown for easy checking of the program. `y` is zero at the root, and as can be seen, an acceptable zero is always found.

The golfed version is low verbosity, displaying only the root per question spec.
> 6 votes

# Answer
# J, 222

*247 - recursion + numerical*

```
NB. multiple lines for visibility
f=:[:-(]$:~[:}.[-%&{.*],#&0@l)`[@.(0>l=:-&#)
r=:1={.
s=:[:=/+/@(2=&*/\])@(,.]*_1^i.@#)@({.@>@(([;];f;j;f f j=.]f f)([:}:(i._5)*])))@|.
u=:0,0([(]*_1^r@k)>:@]^:(1 1-:k=:[:*(0 p.~[)*(p.(,-)))^:_)~]
h=:{.@((n@],]{~[:r[:*p.*(p.n=:{.+-:@-~/))^:_ u)`('n'"_)@.s@|.

```

### Methods

* Using Sturm's theorem to find number of roots.

`f` is polynomial division (recursive)

`s` is Sturm's theorem output: `0` for no real roots, `1` otherwise. It evaluates Sturm's polynomials `([;];f;j;f f j=.]f f)` and checks their behaviour at +/- infinity.
* Using bisection method to avoid divisions by zero, local maxima etc.

`u` scans from 0 to +/- infinity to find an appropriate interval

`((n@],]{~[:r[:*p.*(p.n=:{.+-:@-~/))^:_ u)` evaluates the polynomial at the edges and midpoint then halfs the interval accordingly

### Verification of results

Using J's buildin polynomial root finder as `realRoots`:

```
ti,>([;h;realRoots) each samples
┌──────────────┬────────┬─────────────────┐
│a b c d e     │output  │all real roots   │
├──────────────┼────────┼─────────────────┤
│_1 2 3 4 5    │_1.11029│3.37192 _1.11029 │
├──────────────┼────────┼─────────────────┤
│_1 2 3 4 _5   │0.728727│3.18248 0.728727 │
├──────────────┼────────┼─────────────────┤
│1 2 3 4 5     │n       │                 │
├──────────────┼────────┼─────────────────┤
│1 1 2 _1 _1   │0.728262│0.728262 _0.52236│
├──────────────┼────────┼─────────────────┤
│1 2 3 4 0     │0       │_1.65063 0       │
├──────────────┼────────┼─────────────────┤
│1 2 0 0 1     │_1      │_1.83929 _1      │
├──────────────┼────────┼─────────────────┤
│_1 _1 _1 _1 _1│n       │                 │
└──────────────┴────────┴─────────────────┘

```

*BTW, a simple implementation of Newton's method would be:*

```
f=:3 :'((-(y&p.%y&p.D.1))^:_)0'@|.

```
> 4 votes

# Answer
# C — 340 bytes + 25 points for numerical approximation = 365

To compile `gcc -o quartic quartic.c -lm`, to run `./quartic a b c d e`. Uses Newton–Raphson method, no big whoop. Using deterministic methods, I can't see getting anywhere near this compact.

```
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define C(x) atof(argv[x])
int main(int argc,char *argv[]){int i;double a,b,c,d,e,x,y;a=C(1);b=C(2);c=C(3);d=C(4);e=C(5);for(x=0,y=1,i=0;i<100;x=y,i++){y=x-((((a*x+b)*x+c)*x+d)*x+e)/(((4*a*x+3*b)*x+2*c)*x+d);if(fabs(x-y)<1e-09){printf("%.9f\n",y);return 0;}}printf("n\n");return 1;}

```

e.g.

```
$ ./quartic 1 2 3 4 5
n

$ ./quartic -1 2 3 4 5
-1.110290760

$ ./quartic -1 2 3 4 -5
0.728726879

```

Verified via Wolfram|Alpha, results check out.
> 2 votes

# Answer
# bc (driven by bash), score:137 (162 bytes -50 recursion bonus +25 numerical penalty)

```
bc -ql<<Q
n=0
define r(x){if(n++>99){print "n
";halt}
y=x-($1*x^4+$2*x^3+$3*x*x+$4*x+$5)/(4*$1*x^3+3*$2*x*x+2*$3*x+$4)
if(y==x){print x,"
";halt}else r(y)}r(0)
Q

```

This is pretty much the same algorithm as the answer, though it uses recursion to spice it up.

Run as follows:

```
$ ./quartic.sh 1 2 3 4 5
n
$ ./quartic.sh -1 2 3 4 5
-1.11029075952058816917
$ ./quartic.sh 1 2 3 4 -5
.68412431945306971026
$

```

Of course Newton-Raphson has its limitations, and won't necessarily give all real roots in all cases where the exist.

According to WolframAlpha, this one has real roots at -1.9144 and 1.3731:

```
$ ./quartic.sh 1 1 -2 -1 -1
n
$

```

Also there is a very real risk of divide-by-zero in some cases. But this is code-golf, so who cares ;-)
> 1 votes

# Answer
# C, 182 + 25 = 207

This is not the most eleant solution but it is certainly creative. Using iterger pointer conversions, it loops through every possibile value that a double can hold, tries it out, and checks if it equals 0.

```
int main(int z,char **v){double a[5],f=0,r=1;int i=5;while(i-->0)scanf("%lf",a+i);while(++(*(int*)&f)&&r){i=5,r=0;while(i-->0)r+=a[i]*pow(f,i);}if(r)printf(“%f",r);else printf("n");}

```
> 1 votes

# Answer
### Ruby — 132 characters + 25 numerical = 157

```
require'matrix';f=->a,b,c,d,e{a=-a.to_f;Matrix[[0,0,0,e/a],[1,0,0,d/a],[0,1,0,c/a],[0,0,1,b/a]].eigen.eigenvalues.find(&:real?)||?n}

```

I think this toes the line of using native math libraries, but it's a pretty cool demonstration of what can be done with Ruby, as well as an intriguing way to look at solving univariate polynomial equations through the lens of linear algebra.

Basically, `f` just constructs the companion matrix of the equivalent monic quartic and computes its eigenvalues, which is the same thing as finding the roots of the original quartic.
> 1 votes

# Answer
## Javascript/ES6 148

Since only *a* solution is required, I used a Newton solver.

```
f=s=>{a=s.split(' ');for(x=i=0;i++<1e5;x-=y)z=x*x,y=(a[0]*z*z+a[1]*x*z+a[2]*z+a[3]*x+ +a[4])/(4*a[0]*z*x+3*a[1]*z+2*a[2]*x+ +a[3]);return y|0?'n':x}

```

If you don't have Firefox, you can test it without fat arrow :

```
function f(s){a=s.split(' ');for(x=i=0;i++<1e5;x-=y)z=x*x,y=(a[0]*z*z+a[1]*x*z+a[2]*z+a[3]*x+ +a[4])/(4*a[0]*z*x+3*a[1]*z+2*a[2]*x+ +a[3]);return y|0?'n':x}

```

Test : `f('1 -2 5 -12 4')` returns `0.3882914410047445`

**Warning** : This **can fail** for some equations (if `d=0` for example).
> 0 votes

---
Tags: code-golf, math, polynomials
---


title: Output the first 200 primes using TeX

text:
# Question
Title: Output the first 200 primes using TeX
Write a plain TeX program that lists the first two hundred primes (in base-10 notation). Including external files/resources is not permitted. The output may be to the terminal, the log file, or the actual dvi/pdf file, at your option, but should be easily readable to a human; in particular, there must be some delimiter (comma, space, newline,...) between consecutive primes. e-TeX and pdfTeX primitives are permitted. See this answer for a starting place.

Hard-coding the result is permitted, although I do not expect such an answer to win.

The answer with the lowest byte count wins.

# Answer
## 176 bytes (plain TeX without e-TeX or pdfTeX)

```
\let\n\newcount\n~\n\j\n\k2~3\loop\ifnum~<1224{\let\x.\j3\loop\ifnum\j<~\k~\divide\k\j\multiply\k\j\ifnum\k=~\let\x!\fi\advance\j2\repeat\ifx\x., \the~\fi}\advance~2\repeat\end

```

## Algorithm

The algorithm is quite simple. It outputs the first prime number 2 and goes from the next prime number 3 to the 200th prime number 1223. Each number *i* is tested, if the odd number is divisible by 3 up to *i*-1 without even numbers (thanks Howard for the removal of the even numbers).

There is much room for optimizations of the run-time, e.g.:

* The inner loop can be aborted, when the first divisor is found, see the comments.
* The divisions only need to be done up to sqrt(*i*).

The result is a paragraph with comma separated numbers:

>

## Ungolfed version

```
% assign some count registers with short names
\newcount\i
\newcount\j
\newcount\k
% Output first prime number 2
2%
% Start loop with second prime number 3
\i=3 %
\loop
\ifnum\i<1224 % 1223 is 200th prime number
  {% group with curly braces because of the nested \loop
    \let\x=. % \x is changed, if \i is not prime
    % Test for all 2 <= j < i: trunc(i/j)*j == i
    % If true, then j is divisor of i and i is not prime
    \j=3
    \loop
    \ifnum\j<\i
      \k=\i
      \divide\k by \j
      \multiply\k by \j
      \ifnum\k=\i
        \let\x=! % \i is not prime
        % Optimization to break the loop:
        %   \let\iterate\empty
        % Then also \x can be removed: If the loop is not aborted,
        % then \iterate will have the meaning \relax and the
        % test "\ifx\x." can be replaced by "\ifx\iterate\relax".
      \fi
      \advance\j by 2
    \repeat
    \ifx\x.
      , \the\i % output prime number
    \fi
  }%
  \advance\i by 2 % test next odd number
\repeat
\end % end of job

```

## Variant: Output in protocol file, 195 bytes

```
\let\n\newcount\n~\n\j\n\k~2\def\w{\wlog{\the~}}\w~3\loop\ifnum~<1224{\let\x.\j3\loop\ifnum\j<~\k~\divide\k\j\multiply\k\j\ifnum\k=~\let\x!\fi\advance\j2\repeat\ifx\x.\w\fi}\advance~2\repeat\end

```

The result is written to the `.log` file:

```
This is TeX, Version 3.1415926 (TeX Live 2013) (format=tex 2013.5.21)  11 MAR 2014 18:33
**test
(./test.tex
~=\count26
\j=\count27
\k=\count28
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
643
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
809
811
821
823
827
829
839
853
857
859
863
877
881
883
887
907
911
919
929
937
941
947
953
967
971
977
983
991
997
1009
1013
1019
1021
1031
1033
1039
1049
1051
1061
1063
1069
1087
1091
1093
1097
1103
1109
1117
1123
1129
1151
1153
1163
1171
1181
1187
1193
1201
1213
1217
1223
 )
No pages of output.

```

## Variant: Counting prime numbers, 197 bytes

The following variant also counts the prime numbers to get rid of the "hard-coded" 200th prime number. (I have added this variant at the end, because the question would also allow to hard-code *all* prime numbers.)

```
\let\a\advance\let\n\newcount\n\p\n~\n\j\n\k2\p1~3\loop\ifnum\p<200{\let\x.\j3\loop\ifnum\j<~\k~\divide\k\j\multiply\k\j\ifnum\k=~\let\x!\fi\a\j2\repeat\ifx\x., \the~\global\a\p1\fi}\a~2\repeat\end

```
> 11 votes

---
Tags: code-golf, primes
---


# Question
Title: Partially Solve the halting problem for brainf***
To solve the Halting Problem you are given a description of a program, and must determine whether or not it will ever finish. You can never do this for all programs. Yet for programs like (in brainf\***):

```
>

```

It obviously will halt, and for programs like:

```
+[]

```

It obviously will not. Your challenge is to "solve" the halting problem for as many programs as possible. These programs will not use `.` or `,`, and will not have input or output. You will be given a description of the program and must output either "Halts", "Does not halt", or "Unknown". When your program outputs "Halts" or "Does not halt", you have solved the input program. Here are some requirements.

1. It must solve at least an infinite amount of programs.
2. For every program it solves, its solution must be correct.
3. You may only output 1 of the 3 above choices.
4. You may assume that the running computer has infinite time and memory, so XKCD 1266 would not work (the tape is unlimited).
5. No external resources.
6. You may not use a programming language that can actually solve the halting problem.

You may have a non-code-golfed side program that takes a string that is a program, and generates some sort of abstract syntax tree of it if you like. Note, that isn't really scoring per se, but how to determine if one program beats another.

1. If program A solves an infinite number of programs that B doesn't, but B only solves finite or no programs that A solves, A automatically wins.
2. Otherwise, the program with the fewest characters wins. Do not count white space or comments, so do not obfuscate your code.

Tip: Timers won't work. You see, for any time T and given machine, there is an N, such that all programs longer than that have to take more than T time. This means that a timer can only achieve the solution of a finite number of programs, and, as you can see above, solving a finite number of programs doesn't help.

# Answer
## Python, ungolfed spaghetti code

Oh dear.

```
def will_it_halt(instructions):
    tape_length = 1
    LOOP_BOUND = 1000
    registry = [0] * tape_length
    pos = 0

    jumpbacks = []
    reached_states = set()

    pos_instructions = 0
    while True:
        letter = instructions[pos_instructions]
        if letter == "+":
            registry[pos] = (registry[pos] + 1) % 256
        elif letter == "-":
            registry[pos] = (registry[pos] - 1) % 256
        elif letter == ">":
            pos += 1
            if pos >= tape_length:
                registry += [0]*tape_length
                tape_length = len(registry)
        elif letter == "<":
            pos -= 1
            if pos <= 0:
                registry = [0]*tape_length+registry
                tape_length = len(registry)
                pos += tape_length
        elif letter == "[":
            if registry[pos] == 0:
                nests = 1
                while nests:
                    pos_instructions += 1
                    if instructions[pos_instructions] == "[": nests += 1
                    elif instructions[pos_instructions] == "]": nests -= 1

                if jumpbacks == []:
                    reached_states.clear()

            else:
                jumpbacks.append(pos_instructions-1)

        elif letter == "]":
            stripped_registry = [str(x) for x in registry if x != 0]
            translated_pos = pos - (len(registry) - len(stripped_registry))
            state = (translated_pos, pos_instructions, ".".join(stripped_registry))
            if state in reached_states: return "Does not halt"
            elif len(reached_states) > LOOP_BOUND: return "Unknown"
            else:
                reached_states.add(state)
                pos_instructions = jumpbacks.pop()
        pos_instructions += 1
        if pos_instructions >= len(instructions): break
    return "Halts"

```

Pretty brute-forcey solution to the problem: just run the bf code. We assume the tape length is arbitrarily long and that individual cells wrap at 256. At the end of every loop, we store the state of the tape with a set. States are of the form (our position on the tape, our position on the instructions, what the tape looks like with leading 0's stripped).

If we store the same state twice, then we're somewhere in an infinite loop, so the program does not halt. If we store over 1,000 states, then cut losses and return unknown. Once we leave a loop we check to see if we aren't in any larger loops. If not, we're never seeing any of the previous states ever again (at the very least, the instruction position will always be different!) so we can clear the set of states.

This should accurately determine any BF program who's loops aren't longer than 1,000 iterations, as well as many programs that repeat a state before 1,000 iterations in a loop. Not all of them, though: something like "{1 million +'s here}\[-\]\>+\[+-\]" eventually repeats a state, but the \[-\] loop passes 1,000 iterations first.

Some examples:

```
>+>->+>-

```

No loops, so it reaches the end and halts.

```
+[+]

```

Loop ends after 256 iterations, so it reaches the end and halts.

```
+[+-]

```

Eventually repeats the state (0,5,"1"), so it does not halt.

```
+[->+]

```

This doesn't repeat any states but the loop never ends, so it should print "unknown". But the program kind of cheats here. Instead of storing the position on the tape, it adds an offset between the original registry and the stripped one. If all a loop does is translate the tape by some spaces, then it will continue translating it indefinitely (like a life glider), so we can say it does not halt.

```
+[>+]

```

Doesn't translate, doesn't repeat any states, prints unknown.

```
+++++++++++[-]

```

This does halt, but it would print "unknown" if LOOP\_BOUND was 10.

There's a couple of ways to make this smarter. You could obviously increase LOOP\_BOUND to reduce the number of unknowns. You could have smarter handling of nested loops. You could probably do something fancy with BB numbers and the size of loops to better detect if something should halt, but I'm not good enough at CS nor at Python to be able to do that yet.
> 8 votes

# Answer
## GolfScript (23 chars, infinite correct answers)

```
'[]'&!
# 0 if there are brackets, so Unknown
# 1 if there are no brackets, so no looping, so definitely halts
'UnknownHalts'7/=

```
> 1 votes

# Answer
## Awk

A small extension in power from the two examples. If a program contains no loops at all, hence no decisions, it is still obviously determined to halt. Since we're assuming validity of the program, we also assume brackets are balanced and thus need only search for one or the other of the brackets.

```
BEGIN{RS=""}
!/\[/{print "Halts"; exit}
END{print "Unknown"}

```

For the second, it must check first if the loop runs at all, so we must simulate the straight-line code preceding the loop. Then, if the loop returns to the same cell (ie. number of `>`s is equal to the number of `<`s within the loop), and it performs no incs or decs at this cell (ie. for any position-balanced prefix of the balanced loop body, there are no instances of `+` or `-` before the next `<` or `>`, then the cell is unmodified). Implementing this part may take me more time. Ooh, wait, for the first part of checking if the loop runs at all, we can take this same idea and search the pre-loop program for balanced *suffixes* and insist that there be a `+` or `-` (unbalanced).
> 1 votes

# Answer
## Haskell

Here is a really simple example answer. Feel free to include it in your answers (since you including multiple tests in an answer is a good idea.)

```
main=do
    p<-getLine
    if take 3 p == "+[]"
        then putStr "Does not halt"
        else putStr "Unknown"

```

It basically sees if there is a loop in the beginning. If that exact loop doesn't occur in the beginning, it just gives up. It doesn't even work for `++[]`. It does solve an infinite number of programs though, and it is always correct when it solves it.
> 0 votes

---
Tags: code-challenge, brainfuck, halting-problem
---