title: Sum of Numbers of Array

text:
# Question
Title: Sum of Numbers of Array
Given an array (`N`) of integers, check if it is possible to obtain a sum of `S`, by choosing some (or none) elements of the array and adding them.

**Example #1**

```
{1,2,3}
4

```

should output

```
1 (or true)

```

because 1 and 3 can be added to produce 4.

**Example #2**

```
{3,6,2}
0

```

should output

```
1 (or true)

```

because adding none of them together produces 0.

**Example #3**

```
{0,4,3,8,1}
6

```

should output

```
0 (or false)

```

because no combination of the elements in the array can be added to produce 6.

**Example #4**

```
{3, 2 ,0 ,7 ,-1}
8

```

should output

```
1

```

because 2+7+(-1)=8

# Answer
## Mathematica

This is easy in Mathematica. (1) Generate the subsets of your input list, using the `Subsets[]` command (I had originally used `Permutations[]`, which works but produces redundant results), (2) sum the numbers in each subset by mapping the `Total[]` command across the list of subsets, then (3) check to see if the target sum S is represented among those sums with `MemberQ[]`. To be concise, I've shown this below implemented as a single nested command.

Put your inputs in the first line and execute this:

```
list = {0, 4, 3, 8, 1}; target = 6;
MemberQ[Total /@ Subsets[list], target]

```

Assuming one-character variable names, that's 28 bytes of code.
> 3 votes

# Answer
## C#, complexity O(N\*R)

I think this is the first not-exponential solution so far. Complexity - O(N * R); Space - O(R) bytes; where N is length of input array, and R is the difference between sum of positive numbers and sum of negative numbers in array.

On my machine it takes about 15 seconds calculating answer for input array with 1000 randomly generated integers in range \[-10000..10000\]

```
static bool HasSum(int[] a, int s)
{
    int n = a.Length;
    int positiveSum = a.Where(i => i > 0).Sum();
    int negativeSum = a.Where(i => i < 0).Sum();
    if (s > positiveSum || s < negativeSum)
        return false;
    int offset = -negativeSum;
    s += offset;
    int r = positiveSum - negativeSum + 1;
    bool[] map = new bool[r];
    map[offset] = true;
    for (int i = 0; i < n; i++)
        if (a[i] < 0)
        {
            for (int j = 0; j < r; j++)
                if (map[j])
                    map[j + a[i]] = true;
        }
        else
        {
            for (int j = r - 1; j >= 0; j--)
                if (map[j])
                    map[j + a[i]] = true;
        }
    return map[s];
}

```
> 3 votes

# Answer
# Ruby - the recursive brute force is the best brute force

```
def subsetSum(n,s)
  n.sort!  #ruby checks if the array is already sorted, which doesn't take long
  return true if (s==0) || n.include?(s)  #pretty sure this gets cached
  if n[-1] > s  #(optional, will fail in some scenarios with negatives)
    n.delete_at(-1)  #remove last number if it's over S
    return subsetSum(n,s)
  end
  if n.length>0
    t=n.delete_at(n.length - 1) #length for safety
    return true if subsetSum(n,s-t)
    return true if subsetSum(n,s)  #check with and without the last number used
  end
  false
end

```

example usage: `subsetSum([2,3,4],7) => true` Warning\* will fail when negative numbers are used, I need to go right now and will try to fix the issue later.

# Alternative solution (unoptimized brute force)

```
def subsetSum(n,s)
  return true if s==0
  (0..n.length).each{|x|
    n.combination(x).each{|y|
      return true if y.inject(:+) == s
    }
  }
  return false
end

```

(this one fully works, but is less effective)
> 2 votes

# Answer
## Python

Much like the ruby solution.

```
def f(l, s):
    if s == 0: return True
    if l == []: return False
    return f(l[1:], s) or f(l[1:], s - l[0])

l = list(input())
s = int(input())
print f(l, s)

```

Input format:

```
[1,2,3]
4

```

to stdin.
> 2 votes

# Answer
# Clojure

Function to generate all sub-sets, then checks if any add up!

```
(fn [s n]
    (let [genfun (fn [s]
                 (reduce
                         (fn [init e]
                             (set (concat init (map #(conj % e) init) [[e]])))
                         [[]] s))]
        (some #(= n %)
              (map #(reduce + %) (genfun s)))))

```
> 2 votes

# Answer
### R, create all possible combinations and their sum

```
l=lapply;!S|S%in%unlist(l(l(seq_along(N),combn,x=N),colSums))

```

The command returns `TRUE` or `FALSE`.

`N` and `S` are variables, e.g., `N <- c(1, 2, 3)` and `S <- 4`.
> 1 votes

# Answer
# Haskell

Very simple, just take all the subsets of the input array and check if any of them sum to the given number.

```
subsets [] = [[]]
subsets (x:xs) = [x] : subsets xs ++ (map (x:) (subsets xs))

f xs n = any ((==n).sum) (subsets xs)

```
> 1 votes

# Answer
**Rust**

```
  fn check(array: &[int], s:int) -> bool{
      if s ==0 {
        return true;
      }
      if array == [] {
        return false;
      }
      return (check(array.slice(1, array.len()), s) || check(array.slice(1,array.len()), s - array[0]));
  }
 fn main(){
    let  a = ~[1,2,3];
    println!("{}",check(a,0));
  }

```

I just copied **quasimodo's** solution in rust
> 1 votes

# Answer
# C# LINQ

f has to be initiated to null before assigning the lambda expression because it is recursive and the compiler will complain about f not being initialised if I try and declare f and assign to it on the same line. e.g

```
Func<int, int[], int> f = (s, a) => a.Where((n, i) => s == 0 | (s - n) == 0 | f(s - n, a.Where((_, j) => i != j).ToArray()) == 1).Any() ? 1 : 0;

```

Working program below.

```
class Program
{
    public static void Main()
    {
        Func<int, int[], int> f = null;
        f = (s, a) => a.Where((n, i) => s == 0 | (s - n) == 0 | f(s - n, a.Where((_, j) => i != j).ToArray()) == 1).Any() ? 1 : 0;
        Console.WriteLine(f(5, new[] { 2, 2, 9, 1 }));
    }
}

```
> 1 votes

# Answer
# Haskell

```
import Control.Monad

checkSum :: [Int] -> Int -> Bool
checkSum xs x = elem x . map sum . filter (not . null) . filterM (const [True, False]) $ xs

```

A simpler Haskell formula that makes use of the list monad. The algorithm is broken down below:

```
-- Take the list
xs
-- Compute the power set of this list
filterM (const [True, False])
-- Filter out the empty set from the result
filter (not . null)
-- Add up each subset of the power set
map sum
-- Check and see if any of the sums is equal to the value
elem x

```
> 1 votes

# Answer
# Haskell

Unlike the most other solutions, by computing the set of all possible sums, we often get better complexity than by constructing the sums of all possible subsets. In particular, if the numbers are small, the size of the set is bounded by *t=Σ|nₖ|*, so the whole algorithm is *O(n t log t)*.

```
import qualified Data.IntSet as S

extend :: S.IntSet -> Int -> S.IntSet
extend set n = set `S.union` (S.map (+ n) set)

sums :: [Int] -> S.IntSet
sums = foldl extend (S.singleton 0)

canSumTo :: Int -> [Int] -> Bool
canSumTo s = S.member s . sums

```

Or as a one-liner (with swapped arguments):

```
canSumTo' :: [Int] -> Int -> Bool
canSumTo' = flip S.member . foldl (\set n -> S.union set (S.map (+ n) set)) (S.singleton 0)

```
> 1 votes

# Answer
## APL

Now that the character count doesn't matter, here's some ungolfed APL:

```
canSumTo ← {
    ⍝ get all subsets
    subsets ← {
        ⍝ the bits for [1..2^length] each form
        ⍝ a bitmask for a subset
        bitmasks ← ↓⍉((⍴⍵)/2)⊤⍳2*⍴⍵
        ⍝ apply each bitmap to the input
        /∘⍵¨bitmasks
    }⍺

    ⍝ does any of the subsets of ⍺ sum to ⍵?
    ⍵ ∊ +/¨subsets
}

```

Then:

```
      1 2 3 canSumTo 4
1
      3 6 2 canSumTo 0
1
      0 4 3 8 1 canSumTo 6
0
      3 2 0 7 ¯1 canSumTo 8
1

```
> 0 votes

# Answer
# **Java**

golfed (223 chars):

```
int r(int s,int[] a){for(int i=0;i<a.length;i++){if(s==0|(s-a[i])==0|r(s-a[i],s(a,i))==1)return 1;}return 0;}
int[] s(int[] a,int k){int[] b=new int[a.length-1];for(int i=0;i<a.length-1;i++){b[i]=a[i+(k>i?0:1)];}return b;}

```

formatted:

```
class M {
    public static void main(String[] a) {
        System.out.println(r(6, new int[] { 0, 4, 2, 8, -1 }));
    }

    static int r(int s, int[] a) {
        for (int i = 0; i < a.length; i++) {
            if (s == 0 | (s - a[i]) == 0 | r(s - a[i], s(a, i)) == 1) {
                return 1;
            }
        }
        return 0;
    }

    static int[] s(int[] a, int k) {
        int[] b = new int[a.length - 1];
        for (int i = 0; i < a.length - 1; i++) {
            b[i] = a[i + (k > i ? 0 : 1)];
        }
        return b;
    }

}

```
> 0 votes

# Answer
## Fortran

Algorithm is as follows:

1. Check if the sum of the array is less than `S`
2. Check if any of the elements of the array equals `S`
3. Sort array
4. Slice linear elements of array & check if sum of slice is `S`
5. Sum elements by jumping `i` spaces

I have omitted the module `quicksort` but it does exactly what it sounds like it does. It passed all the test cases above, but it does fail on the array `0,-1,3,5,7` when asked for 11 (requires cells 1,4,5 (0,3,4 for those stuck on 0-indexes) which can't be done for slicing--I am working on fixing this)

```
program rand_array_sum
   use quicksort
   implicit none
   integer, dimension(:), allocatable :: array
   integer :: n, s

   print *,"Enter number of cells in array"
   read(*,*) n; allocate(array(n))
   print *,"Enter comma-separated integers in array:"
   read(*,*) array
   print *,"What is the sum you want?"
   read(*,*) s

   if(s==0) then
      print *,1
      stop
   endif

   if(sum(array)< s) then
      print *,0
      stop
   endif
   if(any(array==s)) then
      print *,1
      stop
   endif

   call sort(array)
   print *,"Sorted array:",array
   call sum_array(n,array,s)

 contains
    subroutine sum_array(n,a,s)
      integer, intent(in) :: n, a(n), s
      integer :: i, j, b
! linear slices
      do i=1,n
         do j=1,i
            !print '("i=",i0,"  j=",i0,"  b=",i0)',i,j,abs(i-j)
            b=abs(i-j)
            if(sum(array(j:n-b))==s) then
               print *,1
               return
            endif
         enddo
         print *,""
      enddo
! jumping slices
      do i=2,n
         do j=1,n-i+1
            if(sum(array(j:n:i))==s) then
               print *,1
               return
            endif
         enddo
      enddo
! if all as failed, then it cannot be done
      print *,0
    end subroutine sum_array
end program rand_array_sum

```
> 0 votes

# Answer
# k/q

```
k){|/y=+/'+x*(-#x)#+0b\:'!*/(#x)#2}

```

this is an adaptation of the `s` function from http://kx.com/q/greplin.q

`s n` returns the bitmasks for the power set of a set of count n

i then simply apply the mask matrix to the vector, sum them all up and look for the number in question

ungolfed and converted back to q, and with the examples:

```
q)s:{neg[x]#flip 0b vs/:til prd x#2}
q)f:{any y=sum each flip x*s count x}
q)f[1 2 3;4]
1b
q)f[3 6 2;0]
1b
q)f[0 4 3 8 1;6]
0b
q)f[3 2 0 7 -1;8]
1b
q)

```
> 0 votes

# Answer
# JavaScript

An homage to / shameless ripoff of quasimodo's solution.

```
function f(l, s) {
    var n = l.slice(1)
    return !s || (!l.length ? false : f(n, s) || f(n, s - l[0]))
}

```
> 0 votes

# Answer
### Ruby

This is a succinct way to do it in Ruby using `Array#combination` but has the unfortunate consequence of performing the calculation of all possible combinations of sub-sums in `array` and then checking to see if the given `sum` is possible. With a large array, that is likely to be a lot of needless calculation.

```
def contains_sum?(array, sum)
  [*1..array.size].reduce([]) { |x, i| x + array.combination(i).to_a }
                  .map { |c| c.reduce(:+) }.push(0).include?(sum)
end

```

Here's a version that isn't a one-liner, but tries to avoid calculating more sums than it has to:

```
def contains_sum?(array, sum)
  return true if sum == 0 || array.include?(sum)
  [*2..array.size].each do |i|
    return true if array.combination(i).detect { |c| c.reduce(:+) } == sum
  end
  false
end

```
> 0 votes

# Answer
# Haskell

We don't care which sets sum to the value, only whether any exists, so we need not ever compute the power-set, only the sums of the elements of the power-set. In particular,

**F**(*S*) := { L | L ∈ **Power**(*S*) }

**F**(∅) = {0}

**F**(*S*) = { **x** \+ *s* | *s***F**(*S***x**) } ⋃ **F**(*S***x**) ∀ **x***S*

The following recursive definition arises naturally.

```
sums [] = [0]
sums (x:t) = sums t >>= \y -> [x+y,y]

possible n xs = elem n xs || elem n $ sums xs

```

`possible` is a function whose first argument is a target number, and whose second argument is a list (array) to search for the target sum within. I added a test for inclusion before a test for summation, as that both makes the search faster and makes searching of infinite lists containing the target much faster. I might make this more ~~complicated~~ sophisticated later on.

## Edit 1

I found that my code didn't work well for infinite lists \*not\* containing the target, so I optimized my code to use a `scanl`, thereby performing a lazy search and increasing the speed of infinite lookups dramatically.

```
import Data.List

sums :: Integral a => [a] -> [[a]]
sums = scanl (\acc x -> [i + j|j<-[x,0],i<-acc]) [0]

possible :: Integral a => a -> [a] -> Bool
possible n xs = any (elem n) (sums xs)

```

The order of the binds in the generator matters; switching the order of `i` and `j` reduces the performance speed. Also, the order of `[x,0]` matters, as it ensures that each successive element of the scan will begin with the sums including the new element, instead of starting with the ones already seen. This does not change the speed of advancing in the scan, but it increases the speed of identifying a scan containing the target.
> 0 votes

---
Tags: popularity-contest
---


title: recursive power algorithm

text:
# Question
Title: recursive power algorithm
Have a look at my (javascript) version of a O(log(n)) xn algorithm:

```
function pow(x,n)
{
     return n==0?1:n==1?x:n==2?x*x:pow(pow(x,(n-n%2)/2),2)*(n%2==0?1:x);
}

```

Can you get it shorter?

# Answer
> 3 votes
If you don't mind using a global variable:

```
return n?(t=pow(x,n>>1))*t*(n%2?x:1):1

```

Through some ingenious trickery, Howard devised a clean alternative:

```
return n?(n%2?x:1)*(x=pow(x,n>>1))*x:1

```

And Peter Taylor managed to shave one character:

```
return(n%2?x:1)*(x=n?pow(x,n>>1):1)*x

```

Even shorter based on ratchet freak's idea:

```
return(n%2?x:1)*(n?pow(x*x,n>>1):1)

```

# Answer
> 4 votes
BrainFuck (482 characters)

Solution is modulo 256. Reads n in digit by digit. Each time it sees a new digit d, it raises the current value to the tenth power and then multiplies that by x^d Input must be x followed by single space, followed by n, followed by newline

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

```

# Answer
> 2 votes
```
function pow(x,n)
{
     return n==0?1:n==1?x:pow(x*x,n>>1)*pow(x,n&1);
}

```

removed the `n==2` case,

replaced the `(n-n%2)/2` with `n>>1` (you can also use `n&-2`)

used `x*x` instead of `pow(pow(...),2)`

replaced `*(n%2==0?1:x)` with `*pow(x,n&1)`

# Answer
> 2 votes
## GolfScript (29 chars as function, 24 chars as block)

```
{1@@2base-1%{{.@*\}*.*}/;}:P;

```

without the function wrapper that's

```
1@@2base-1%{{.@*\}*.*}/;

```

It's not recursive, but it is `O(lg n)` time, using the binary decomposition of `n`. Essentially it takes the fact that the recursive `pow` can be made tail-recursive with an accumulator and pushes that to its conclusion:

```
# Stack: a n
1@@
# Stack: 1 a n
2base
# Stack: 1 a [bits of n]
# Reverse the bits so that we loop over them starting at the least significant
-1%
# foreach
{
    # Stack: accum x bit
    # where accum = a^(n%(2^i)) and x = a^(2^i)

    # If the bit is set, multiply the accumulator by x
    {.@*\}*

    # Square x
    .*
}/
# Pop the unwanted a^(2^(2+lg n)) and we're left with a^n
;

```

(There is also the built-in `?` for one char, but I don't think that's in the spirit of this codegolf).

# Answer
> 0 votes
# GolfScript - 33

This feels awfully clumsy but here it goes:

```
{.2/.{2$\P}{;1}if.*@@1&{*.}*;}:P;

```

Usage: `2 11P` -\> `2048`

(Thanks Peter Taylor)

# Answer
> 0 votes
## Java

```
int pow(int x, int n){
    int t=1;
    return n==0?1:(n%2==0?1:x)*(t=pow(x,n/2))*t;
}

```

And if `t` is an initialized class variable, you can remove the first line.

# Answer
> 0 votes
**C++, 44 characters**

```
int p(int x,int n){return !n?1:x*p(x,n-1);}

```

# Answer
> 0 votes
## k4 (38)

fairly straightforward port of the java solution

`{$[y;*/((y-2*r)#x),2#x .z.s/r:_y%2;1]}`

# Answer
> 0 votes
### Haskell, 49 characters

```
x^0=1;x^2=x*x;x^n|odd n=x*x^(n-1)|1>0=x^div n 2^2

```

readable version:

```
x^0 = 1
x^2 = x * x
x^n | odd  x = x * x^(n-1)
    | even x = x ^ (d`div`2) ^ 2

```

The idea to special-case x^2 shamelessly stolen from the asker.

Another 49-character version, requires common subexpression elimination (which GHCi doesn't do in this case) to be efficient:

```
x^0=1;x^n|odd n=x*x^(n-1)|1>0=x^div n 2*x^div n 2

```

# Answer
> -1 votes
In python we have 2 methods for doing this :

```
def p(x,n,l):
    print pow(x,n,l)
def p1(x,n):
    print x**n
p(10,5,52)
p1(10,5)

```

Output corresponding to it is:

```
4
100000

```

The best part in python function is that it helps in modular power also (which is faster than finding power and then mod).In pow (n,m,l) It produces : (n^m)%l as the output.

# Answer
> -1 votes
## PHP

```
function p($x,$n){return($n>1)?p($x*$x,$n-1):$x}

```

---
Tags: code-golf, tips
---


title: Anti-aliased ASCII Aureoles

text:
# Question
Title: Anti-aliased ASCII Aureoles
Consider the following ASCII image of five concentric anti-aliased ASCII aureoles:

```
                 ........
            .@..............@.
        .....                .....
      .@..    ...@@@@@@@@...    ..@.
    .@.    ..@@..        ..@@..    .@.
   .@.   .@@.    ........    .@@.   .@.
  .@    @@    .@@@@@..@@@@@.    @@    @.
 .@    @.   .@@.          .@@.   .@    @.
 @.   @@   @@.   @@@@@@@@   .@@   @@   .@
.@   .@   .@.   @@@.  .@@@   .@.   @.   @.
.@   @@   @@   @@   @@   @@   @@   @@   @.
.@   @@   @@   @@   @@   @@   @@   @@   @.
.@   .@   .@.   @@@.  .@@@   .@.   @.   @.
 @.   @@   @@.   @@@@@@@@   .@@   @@   .@
 .@    @.   .@@.          .@@.   .@    @.
  .@    @@    .@@@@@..@@@@@.    @@    @.
   .@.   .@@.    ........    .@@.   .@.
    .@.    ..@@..        ..@@..    .@.
      .@..    ...@@@@@@@@...    ..@.
        .....                .....
            .@..............@.
                 ........

```

You must write a program to draw a given subset of the above circles in as few characters as possible.

The input is either five booleans in your choice of formatting (be it `1 1 1 1 1` or `[False, True, False, False, True]`), with the first boolean corresponding to the inner-most circle, or an integer where the least-significant bit corresponds to the inner circle (e.g. `1 0 0 1 1` is equivalent to `25`).

Output for `1 1 1 1 1`/`31`: see above.

Output for `1 0 1 0 1`/`21`:

```
                 ........
            .@..............@.
        .....                .....
      .@..                      ..@.
    .@.                            .@.
   .@.           ........           .@.
  .@          .@@@@@..@@@@@.          @.
 .@         .@@.          .@@.         @.
 @.        @@.              .@@        .@
.@        .@.                .@.        @.
.@        @@        @@        @@        @.
.@        @@        @@        @@        @.
.@        .@.                .@.        @.
 @.        @@.              .@@        .@
 .@         .@@.          .@@.         @.
  .@          .@@@@@..@@@@@.          @.
   .@.           ........           .@.
    .@.                            .@.
      .@..                      ..@.
        .....                .....
            .@..............@.
                 ........

```

Output for `0 0 0 1 0`/`8` (note the leading whitespace):

```
              ...@@@@@@@@...
           ..@@..        ..@@..
         .@@.                .@@.
        @@                      @@
       @.                        .@
      @@                          @@
     .@                            @.
     @@                            @@
     @@                            @@
     .@                            @.
      @@                          @@
       @.                        .@
        @@                      @@
         .@@.                .@@.
           ..@@..        ..@@..
              ...@@@@@@@@...

```

The aureoles themselves must be exactly as presented above. However, trailing whitespace is optional. Also, if some outer aureoles are missing, it is up to you whether your program outputs the leading empty lines or the trailing empty lines.

# Answer
# JavaScript (E6) 272 ~~314~~

On par with the other JS answers, a function returning a string. Add 13 byte if an output statement is requested (console.log()).
The function parameter is an array of 5 truthy/falsy values.

**Edit** Shorter implementation of the same algorithm
The string at line 2 codify the lower right quarter of the rings. The others are obtained thanks to simmetry

* ' ' space mark line end
* digit (1..9) mark a sequence of blank spaces
* hex digit (A..F or a..f) mark a sequence of symbols, if lowercase '.' else '@'

Rendering the lines, it checks the boolean params and output symbols or an equal number of spaces

```
F=f=>
  [for(c of(l=d=0,o=t=[],'A3B3B3B3Aa 1aC3aAa3Aa3Aa D3aB3B3aA1 5aBa3aA4Aa1 aEa4B4Aa2 d4aBa3aAa3 4bBb4aAa4 Dc4bAa6 8e8 cdAa66 d89 '))
   c<'1'?(l=(t=[o,...t,o]).length/5.1|0,d=1,o='')
   :o=(p=(-c||!f[l+=d]?' ':c>'F'?'.':'@').repeat(-c?(d=1,c):(d=0,'0x'+c-9)))+o+p]
  &&t.join('\n')

```

**Test** In FireFox/FireBug console

```
F([1,0,1,0,1]) (or F[1,,1,,1])

```

*Output*

```
                 ........
            .@..............@.
        .....                .....
      .@..                      ..@.
    .@.                            .@.
   .@.           ........           .@.
  .@          .@@@@@..@@@@@.          @.
 .@         .@@.          .@@.         @.
 @.        @@.              .@@        .@
.@        .@.                .@.        @.
.@        @@        @@        @@        @.
.@        @@        @@        @@        @.
.@        .@.                .@.        @.
 @.        @@.              .@@        .@
 .@         .@@.          .@@.         @.
  .@          .@@@@@..@@@@@.          @.
   .@.           ........           .@.
    .@.                            .@.
      .@..                      ..@.
        .....                .....
            .@..............@.
                 ........

```
> 3 votes

# Answer
# JavaScript (ES5), 359 bytes

Place input into `I`, get output on stdout/console.

```
I=[1,1,1,1,1];a='-----  88880----8988888880--  88888--  0--8988- 66677770- 898- 667766- 0-898-6776- 44440  89- 77- 45555540 89- 76-4554-  0 98-77-554-3333089-67-454-3332 089-77-55-33-1'.replace(/-/g,'   ').split(0);for(i=11;i--;)a.push(a[i]+=a[i].split('').reverse().join(''));console.log(a.join('\n').replace(/\d/g,function(d){return I[d>>1]?'.@'[d&1]:' '}))

```
> 4 votes

# Answer
## JavaScript ES6, 567b (WIP)

Execute this code in the JS/NodeJS console to display the result in the console.

the array "a" at the beginning contains the input.

```
a=[1,0,1,0,1];(z=a=>a+a.split("").reverse().join(""))(b=["                 0000","            010000000","        00000        ","      0100    2223333","    010    223322    ","   010   2332    4444","  01    33    4555554"," 01    32   4554     "," 10   33   554   7777","01   23   454   7776 ","01   33   55   77   9",""].map(z).join("\n")[r="replace"](/0/g,a[0]?".":" ")[r](/1/g,a[0]?"@":" ")[r](/2/g,a[1]?".":" ")[r](/3/g,a[1]?"@":" ")[r](/4/g,a[2]?".":" ")[r](/5/g,a[2]?"@":" ")[r](/6/g,a[3]?".":" ")[r](/7/g,a[3]?"@":" ")[r](/9/g,a[4]?"@":" "))[r]("\n\n","\n")

```
> 2 votes

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


# Question
Title: Resolve doubling and tripling actions in Dominion
## Inspiration

This question is inspired by the cards Throne Room and King's Court from the popular deck-building card game Dominion.

As part of one's turn, one plays a sequence of actions. These two particular actions cause the next-played action to repeat two or three times\*. Other "generic" actions cause specific game effects, but we won't be interested in the particulars, simply labelling them with letters.

The interesting case is when a Throne Room or King's Court affects another Throne Room of King's Court, causing the doubling or tripling effect to itself be doubled or tripled. Long chains of Throne Rooms, King Courts, and multiplied actions can confuse even experienced Dominion players.

Your goal is to write code that correctly resolves these chains, using as few bytes as possible. I'll describe the program requirements before explaining how the chains resolve in the Dominion rules.

\*Technically, you choose the action affected as part of resolving Throne Room or King's Court, but this view is cleaner for this challenge.

## Program Requirements

Write a *program* or *named function*. It should take in the chain of actions played (STDIN or function input), and output or print the resulting chain of actions from the effects of doubling and tripling. Fewest bytes wins.

## Input

A string representing the sequence of actions played. Generic actions are represented by capital letters `A` through `Z`. The special doubling action Throne Room is represented by the character `2`, and the tripling action King's Court by `3`,

The number of characters (actions) will be between 1 and 30, inclusive. You may have the input end in a newline if you wish.

Example input: `WA23G3GA`

## Output

A string of capital letters`A` to `Z`. This should be the sequence of generic actions that results from resolving the doubling and tripling effects, in the order than they happen.

You may have the output end in a newline if you wish. There should be no additional characters otherwise.

Example output: `WAGGGGGGAAA`.

## How doubling and tripling works in Dominion

Here, I'll go through how chains of Throne Rooms (`2`'s) and King's Courts (`3`'s) work as per the Dominion rules.

After you play a `2`, the next action to be resolved happens twice. So, if you first play `2`, then `A`, you get `A` happening twice.

```
2A -> AA

```

Similarly,

```
A2BC -> ABBC
3DE -> DDDE
3N2BC3XY2 -> NNNBBCXXXY

```

Note in the last example that the final `2` had nothing to double, so it had no effect.

The interesting thing happens when doubling or tripling effects are themselves doubled or tripled. For example,

```
22AB -> AABB

```

First, you play `2`. Then, you play another `2`, which is doubled from the previous `2`. As a result, the next *two* actions are doubled. First, the two copies of `A` resolve. Then, the copies of `B` resolve.

Note that `A` is not quadrupled: after the first copy of `2` acts on the first `A`, the next copy acts on the next unresolved action, which is `B`. Without the `B`, we'd have

```
22A -> AA

```

where the second copy of `2` is waiting for the next action to double, but no action comes.

Finally, let's look at a complex example.

```
223BCDE -> BBBCCCDDE

```

As before, the first `2` causes the second `2` to be doubled. So, the next two actions will be doubled. The first copy of `2` doubles the next action `3`, which must be resolved completely before resolving the next copy of `2`. The first copy of `3` triples `B`, and the second copy triples `C`. Now, the still-waiting second copy of `2` doubles the next still-unresolved action, which is `D`. After this, no doubling or tripling effects remain, and the final action `E` simply happens.

## Test cases

These are given as `(input,output)`.

```
(FY, FY)
(A2BC, ABBC)
(3DE, DDDE)
(3N2BC3XY2, NNNBBCXXXY)
(WA23G3GA, WAGGGGGGAAA)
(32, )
(33RST, RRRSSSTTT)
(2A32B2CDEFG, AABBCCDDEEFG)
(A2A323AB2CD2D2E3ABC, AAAAAABBBCCDDDDEEAAABBBC)
(P22LL3Q2Q22T, PLLLLQQQQQTT)
(322322ABCDEFGHIJKLMN, AABBCCDDEEEFFGGHHIJKLMN)

```

# Answer
## GolfScript (29 26 bytes)

```
](1/{\1+(3&@*.23-\1$-@+}/;

```

Online demo

### Dissection

This slightly abuses the loose typing of GolfScript. The stack of how many times to repeat subsequent actions starts out as an array and later turns into a string - but `1+` appends a 1 and `(3&` pops the first value and correctly puts it in the range `0` to `3` regardless of the type change.

```
](         # Push an empty array under the input string to serve as rep stack
1/{        # Loop over the input string as a series of 1-char strings
           #   Stack is ... reps ch
           #   where the ... covers zero or more strings which will be output
  \        #   Bring the rep stack to the top
  1+(      #   Push a `1` on the bottom of it to avoid underflow and then pop
  3&       #   Coerce to correct range, because if rep stack is a string then
           #   we just got an ASCII value
  @*       #   Apply repetition to the 1-char string: it's now an n-char string
  .23-     #   Duplicate it and remove chars '2' and '3': this becomes output
  \1$-     #   Get the original copy and remove the output string's chars
           #   So the stack is now ... reps output non-output
           #   where non-output is either an empty string or a string of '2's
           #   or '3's
  @+       #   Push non-output onto the repetition stack
}/         # Loop
;          # Pop whatever's left of the repetition stack

```
> 5 votes

# Answer
# Javascript - ~~162~~ 152 bytes

Minified:

```
F=I=>{L=c=>S.length;p=c=>L()?S.shift():d=>{};S=[(x=>/\d/.test(x)?(c,b)=>{for(c=p(),b=x;b--;)c();}:c=>s+=x)(m)for(m of I)];for(s='';L();)p()();return s;}

```

Expanded:

```
F = I => {
    L = c => S.length;
    p = c => L() ? S.shift() : d => {};
    S = [ (x => /\d/.test( x ) ?
        (c,b) => {
            for( c = p(), b = x; b--; )
                c();
        } : c =>
            s += x
        )(m) for( m of I ) ];

    for( s = ''; L(); )
        p()();

    return s;
}

```

I'm guessing the stack-based golf languages will kill on this one, since it's basically an exercise in function stacking. :P

### Sample Outputs

```
F('3N2BC3XY2')
"NNNBBCXXXY"

F('WA23G3GA')
"WAGGGGGGAAA"

F('A2A323AB2CD2D2E3ABC')
"AAAAAABBBCCDDDDEEAAABBBC"

F('322322ABCDEFGHIJKLMN')
"AABBCCDDEEEFFGGHHIJKLMN"

F('FY')
"FY"

F('')
""

```
> 4 votes

# Answer
# C, 115 111 bytes

Uses standard input/output.

Saved 4 by using `memset` and making the stack go in the other direction.

```
char*i,X[222],*s=X+99;main(){for(gets(i=X);*i;i++)*i<55?s=memset(s-*s,*i-49,*s+1):putchar(*i)**s?--*s,--i:++s;}

```

**Ungolfed**

```
#include <stdio.h>
#include <stdlib.h>
char I[99], S[99], *i = I, *s = S+66;
int n;
int main()
{
    gets(I);
    for(;*i;)
    {
        if(*i < '5') {
            n = *s;
            s[0] = s[1] = s[2] = *i - '1';
            s += n;
            i++;
        } else {
            putchar(*i);
            if(*s)
                --*s;
            else
                --s, ++i;
        }
    }
    return 0;
}

```
> 3 votes

# Answer
## Python (84)

```
S='1'*99
R=''
for c in input():q=int(S[0])*c;S=q*(c<'A')+S[1:];R+=q*(c>'3')
print(R)

```

`S` is the stack of multipliers (top if front). It's initialized with enough `1`'s to handle unmultiplied actions.

Depending on whether the current action `c` is generic or not, we add its multiplied result either to the output `R` or to the stack of multipliers `S`.

Everything is represented as a string rather than a list of chars. Because strings are immutable, we unfortunately can't use `pop` or element assignment on them.
> 0 votes

---
Tags: code-golf, game
---


title: Unique code generation

text:
# Question
Title: Unique code generation
As input, you are given a positive integer *n*. Output a code in response. Each *n* should generate a unique code. There are some constraints on the code that it outputs:

* The code must be 7 or more characters long in based on the input.
* The code will be have only 7 characters when input string is less than 676000 and must be unique.
* The code always begins with `ST`
* The third and fourth characters are letters from A-Z
* The remaining characters are numbers.

so if 1 then STAA001

```
  2 then STAA002

```

upto 999 then STAA999

```
  1K then STAB000

```

this will continue unto 676599 then STZZ999, (still this total count is 7) so after this for 676000 then STAA0000 (count is 8) and so on.

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

KMT's original post for reference:

> I need the generate the code using input value. The code must be 7 or more character Consider Sample code STAA000 in which 'ST' is always constant and next to characters changes based on the input they must alphabets from A-Z and the remaining characters are number.
>
> EX:
>
> ```
>   Input         Result
>
>   1. 100              STAA100
>   2. 2201             STAB201
>   3. 676001           STAA0001
>   4. 677111           STAA1111
>
> ```

# Answer
## CJam, 9

```
"STAA00"r

```

Just prints the number back, no fancy algorithm.
> 4 votes

# Answer
# Pyth, 9

```
p*w3"STAA

```

Examples:

```
$ pyth -c 'p*w3"STAA' <<< 0
STAA000
$ pyth -c 'p*w3"STAA' <<< 677111
STAA677111677111677111

```

This is exactly equivalent to the following python 3 code:

```
print("STAA", end=input()*3)

```

The `*3` is necessary to guarantee the result is at least 7 characters.
> 0 votes

---
Tags: code-golf
---


title: Riemann Series Theorem

text:
# Question
Title: Riemann Series Theorem
The Riemann series theorem states that the terms of a conditionally convergent series can be permutated such that the resulting series converges to an arbitrary value.

# The Challenge

Write a program or function that takes in three parameters via stdin (or equivalent) or as parameters:

* The expression for the sequence `x_n` (with variable `n`). The exact format (e.g., whether a power is represented as `^`, `pow()` or `**`) is irrelevant and may be chosen to fit your language. Alternatively you may pass a function directly as an argument. The definition of the function does not count towards the byte count.
* A value `S` that we want to approach. Numerical values only are fine, you don't need to support mathematical expressions.
* A threshold `t>0`. Numerical values only are fine here as well.

Your program/function must output (to stdout or equivalent) resp. return a space- or newline-separated list `p_1, ..., p_N` of indices.

Your output must satisfy the condition that the sum from `k = 1..N` over `x_(p_k)` differs from `S` no more than `t` in terms of the absolute difference. In other words, it must satisfy

So far, since the output will be a finite number of indices, the order would not matter. Therefore, another restriction applies: with decreasing threshold `t`, you may only *add* indices to the output (assuming a fixed `S`).

In other words, for a fixed `S`, if `t_1 < t_2` and `[x_1, ..., x_N]` is a solution for `t_2`, then a solution for `t_1` must be of the form `[x_1, ..., x_N, ..., x_M]` with `M >= N`.

# Details and Restrictions

* The order of the arguments may be changed to suit your needs.
* Provide an example call with the arguments from the example below. Ideally, post a link to an online interpreter/compiler.
* `eval` and the like are explicitly allowed for the purpose of evaluating mathematical expressions.
* Sequences are 1-based, so the first index is 1.
* You don't need to take special care of big integers or floating point problems. There will be no extreme test cases such as using machine precision as the threshold.
* Standard loopholes apply.
* You may assume that the sequence passed to your program is conditionally convergent, i.e. that it is possible to solve the task with the given parameters.

# Example

Say your program is in a file `riemann.ext`, then a call might be

```
./riemann.ext "(-1)^(n+1)/n" 0.3465 0.1

```

# Scoring

This is code-golf. The shortest program in bytes (UTF-8 encoding) wins. In case of a tie, the earlier entry wins.

# Answer
> 1 votes
## Python – 88

```
def R(x,S,t):
 I=[0,0]
 while abs(S)>t:
    i=I[S>0]=I[S>0]+1
    if x(i)*S>0:S-=x(i);print i,

```

`I` stores the indices for positive and negative numbers and to reduce the number of variables, I do not sum up to `0` until I reach `S`, but subtract from `S` until I reach `0`.

I am not entirely sure whether this complies with the restrictions on the input.

The used algorithm should be very nice for a stack-based language.

# Answer
> 4 votes
# Haskell, ~~161~~ ~~158~~ 144

because Haskell can deal with infinite lists, instead of doing the parsing stuff this solution receives an infinite list as the sequence.

```
r l s t=unwords[show$[i+1|i<-[0..],l!!i==x]!!0|x<-s%filter(>0)l$filter(<0)l]where(g%j@(p:o))y@(n:b)|abs g<t=[]|g<0=n:((g-n)%j)b|0<1=p:((g-p)%o)y

```

example output:

```
*Main> let harm = zipWith (*) (cycle [1,-1]) (map (1/) [1..]) -- the alternating harmonic numbers
*Main> r harm 3 0.001
"1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 2 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197 199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307"

```

# Answer
> 3 votes
### Haskell, 206 characters

```
import Data.List
r t e f=unwords.map(show.snd)$(\(x,y:_)->x++[y])$span(\(s,_)->abs(t-s)>e)$m 0$partition(<(0,0))$zip f[1..] where m s(a@((b,c):d),w@((x,y):z))|s<t=(x+s,y):m(x+s)(a,z)|1>0=(b+s,c):m(b+s)(d,w)

```

The sequence itself is an implicit last argument. Usage:

```
r 2 0.001 [(-1)**(n+1) / n | n <- [1..]]

```

Beaten before even having been posted, but - oh well. Posted anyways. I also took the liberty of accepting an infinite list as my first argument.

readable version:

```
import Data.List
import Debug.Trace
riemannConverge :: (Integral ix, Num v, Ord v, Show ix, Show v) => (ix -> v) -> v -> v -> String
riemannConverge target maxError series =
    unwords $
    map (show . \(_,ix) -> ix) $
    (\(xs,y:_) -> xs++[y]) $
    span (\(s,_) -> abs (target - s) > maxError) $
    map (\x -> traceShow x x) $
    mergeNP 0 $
    partition (\(x,_) -> x<0) $
    zip series [1..]
  where
    mergeNP s (nss@((nVal,nIx):ns), pss@((pVal,pIx):ps))
     | s < target = (pVal + s, pIx) : mergeNP (pVal + s) (nss,ps)
     | otherwise  = (nVal + s, nIx) : mergeNP (nVal + s) (ns,pss)

```

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


# Question
Title: Tension on a Graph, Part II: A Rubber Band
This is the second of two challenges about "pulling functions taut". Here is the slightly simpler Part I.

Let's drive *m* nails into a board at positions *(x1, y1)* to *(xm, ym)*. Tie a rubber band to the first and last of those and stretch around the other nails, such that the band traverses all nails in order. Note that the rubber band now describes a piecewise linear parameterised function *(x(t), y(t))* in 2D space.

Now drive another *n* nails into the board, at positions *(x1, y1)* to *(xn, yn)*. If we now remove all of the original *m* nails *except* the first and last one (which the ends of the rubber is tied to), the rubber band will shorten until it's lying taut around the new nails, yielding another piecewise linear function.

As an example, take *m = 12* initial nails at positions *(0, 0), (2, -1), (3/2, 4/3), (7/2, 1/3), (11/2, 16/3), (1, 16/3), (0, 1), (7, -2), (3, 4), (8, 1), (3, -1), (11, 0)*, and *n = 10* further nails at positions *(1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0), (6, 2), (7, 1), (6, 0)*. The following three plots show the process described above:

For larger version: Right-click --\> Open in new tab

And here is an animation of the rubber band tightening if you have some difficulty visualising it:

## The Challenge

Given two lists of "nails", plot the taut rubber band around the second list if it starts from the shape traversing all the nails in the first list.

You may write a program or function and take input via STDIN, ARGV or function argument. You can either display the result on the screen or save an image to a file.

If the result is rasterised, it needs to be at least 300 pixels on each side. The final rubber band and nails must cover at least 75% of the horizontal and vertical extent of the image. The length scales of *x* and *y* have to be the same. You need to show the nails in the second set (using at least 3x3 pixels) and the string (at least 1 pixel wide). You may or may not include the axes.

Colours are your choice, but you need at least two distinguishable colours: one for the background and one for the nails and the string (those may have different colours though).

You may assume that all nails in the second list are at least 10-5 units away from initial shape of the rubber band (so that you don't need to worry about floating-point inaccuracy).

This is code golf, so the shortest answer (in bytes) wins.

## More Examples

Here are two more examples:

```
{{1, 1}, {3, 3}, {2, 4}, {1, 3}, {4, 0}, {3, -1}, {2, 0}, {4, 2}}
{{2, 1}, {3, 2}, {1, 2}, {4, 1}}

```

```
{{1, 1}, {3, 1}, {3, 3}, {1, 3}, {1, 5}, {3, 5}, {-1, 3}, {-1, 0}, {3, 4}, {5, 1}, {5, -1}, {7, -1}, {3, 7}, {7, 5}}
{{0, 0}, {0, 2}, {0, 4}, {0, 6}, {2, 0}, {2, 2}, {2, 4}, {2, 6}, {4, 0}, {4, 2}, {4, 4}, {4, 6}, {6, 0}, {6, 2}, {6, 4}, {6, 6}}

```

And here is one example that shows the significance of two of the initial nails remaining. The result should be *b* and **not** *a*:

```
{{0, 0}, {0, 1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 0}}
{{-0.5, 0.5}}

```

Thanks to Ell for providing this example.

# Answer
> 11 votes
## Python + matplotlib, 688

```
from pylab import*
C=cross
P,M=eval("map(array,input()),"*2)
P,N=[[P[0]]+L+[P[-1]]for L in P,M]
W=[.5]*len(P)
def T(a,c,b):
 I=[(H[0]**2,id(n),n)for n in N for H in[(C(n-a,b-a),C(n-b,c-b),C(n-c,a-c))]if(min(H)*max(H)>=0)*H[1]*H[2]]
 if I:d=max(I)[2];A=T(a,c,d);B=T(d,c,b);return[A[0]+[d]+B[0],A[1]+[sign(C(c-a,b-c))]+B[1]]
 return[[]]*2
try:
 while 1:
    i=[w%1*2or w==0for w in W[2:-2]].index(1);u,a,c,b,v=P[i:i+5];P[i+2:i+3],W[i+2:i+3]=t,_=T(a,c,b);t=[a]+t+[b]
    for p,q,j,k in(u,a,1,i+1),(v,b,-2,i+len(t)):x=C(q-p,c-q);y=C(q-p,t[j]-q);z=C(c-q,t[j]-q);d=sign(j*z);W[k]+=(x*y<=0)*(x*z<0 or y*z>0)*(x!=0 or d*W[k]<=0)*(y!=0 or d*W[k]>=0)*d
except:plot(*zip(*P))
if M:scatter(*zip(*M))
show()

```

Reads two lists of points from STDIN.

**Example**

```
[(0, 0), (2, -1), (3.0/2, 4.0/3), (7.0/2, 1.0/3), (11.0/2, 16.0/3), (1, 16.0/3), (0, 1), (7, -2), (3, 4), (8, 1), (3, -1), (11, 0)]
[(1, 1), (3, 1), (4, 4), (1, 3), (2, 2), (5, -1), (5, 0), (6, 2), (7, 1), (6, 0)]

```

**How it works**

The key to the solution is to work in small, incremental steps. Instead of trying to figure out what happens when we remove all the nails at once, we concentrate on the direct effects of removing just a single nail. We can then remove the nails one by one in an arbitrary order.

Working incrementally means that we must keep track of the intermediate state of the rubber band. Here's the tricky part: merely keeping track of which nails the band runs through is not enough. During the process of removing nails the band can get wound and later unwound around a nail. Therefore, when the band interacts with a nail we must keep track of how many times and in what direction it wraps around it. We do it by assigning a value to each nail along the band like so:

Note that:

* We start counting as soon as the band is tangent to the nail, even though the nail doesn't strictly affect its shape. Recall that, unlike the illustration, our nails are dimensionless. Therefore, if the band becomes tangent to a nail we can't tell which side of the band the nail is on by its position alone---we must keep track of where it *used* to be relative to the band.
* We keep around nails with a value of zero, that is, nails that used to, but no longer hold the band, instead of removing them right away. If we did, it could trigger an unwelcomed chain reaction, while we're trying to keep the effects of each step localized. Instead, nails with a value of zero are considered eligible for removal as part of the bigger process.

Now we can describe what happens at each step:

* We select a nail to remove from the band's current path. A nail is eligible for removal if it's part of the first set of nails (save for the endpoints) or if its value is zero.
* Pretending that the two neighboring nails are fixed, we figure out which nails from the second set or the pair of endpoints the band is going to run through once the selected nail is removed (we don't bother with the rest of the nails from the first set, since they'll eventually all be removed.) We do it in a similar fashion to the solution to Part I. All these nails are on the same side of the band, hence we assign to all of them a value of *1* or *-1*, depending on the side.
* We update the value of the two neighboring nails to reflect the changes to the band's path (easily the trickiest part!)

This process is repeated until there are no more nails to remove:

And here's a more complicated example illustrating the band wrapping around a nail several times:

# Answer
> 5 votes
## Java - 1262 bytes

I know this is probably not golfed as much as it could be.

However, no one else seems to be stepping up to the plate and answering this question, so I will.

First, class "T" - which is a point class - 57 bytes

```
class T{double x,y;public T(double a,double b){x=a;y=b;}}

```

And the main class - 1205 bytes

```
import java.awt.Color;import java.awt.Graphics;import java.util.*;import javax.swing.*;class Q extends JPanel{void d(List<T>a,T[]z){JFrame t=new JFrame();int m=0;int g=0;for(T v:a){if(v.x>m)m=(int)v.x;if(v.y>g)g=(int)v.y;}for(T v:z){if(v.x>m)m=(int)v.x;if(v.y>g)g=(int)v.y;}t.setSize(m+20,g+20);t.setVisible(true);t.getContentPane().add(this);double r=9;while(r>1){r=0;for(int i=0;i<a.size()-1;i+=2){T p1=a.get(i),p2=new T((p1.x+a.get(i+1).x)/2,(p1.y+a.get(i+1).y)/2);a.add(i+1,p2);if(y(p1,p2)>r){r=y(p1,p2);}}}double w=15;List<T>q=new ArrayList<T>();while(w>3.7){w=0;q.clear();for(int e=0;e<a.size()-2;e++){T p1=a.get(e),u=a.get(e+1),p3=a.get(e+2),p2=new T((p1.x+p3.x)/2,(p1.y+p3.y)/2);w+=y(u,p2);int k=0;if(y(p1,a.get(e+1))<.5){a.remove(e);}for(T n:z){if(y(n,p2)<1){k=1;q.add(n);}}if(k==0){a.set(e+1,p2);}}}q.add(a.get(a.size()-1));q.add(1,a.get(0));p=z;o=q.toArray(new T[q.size()]);repaint();}T[]p;T[]o;double y(T a,T b){return Math.sqrt(Math.pow(b.x-a.x,2)+Math.pow(b.y-a.y,2));}public void paintComponent(Graphics g){if(o!=null){for(int i=0;i<o.length-1;i++){g.drawLine((int)o[i].x,(int)o[i].y,(int)o[i+1].x,(int)o[i+1].y);}g.setColor(Color.blue);for(T i:p){g.fillOval((int)i.x-3,(int)i.y-3,6,6);}}}}

```

Example:

To run, call the "d" function with a List of points and an array of nails (yeah, I know, weird). What it does:

* creates a list of points that represent the lines - that is, all the points in between the lines.
* repeats an algorithm repeatedly to these points so that the each point is the average of the two points around it.
* When the points don't seem to be moving much anymore, I draw between any nails that they are touching.

I am not sure if axes in pixels is ok. It will always take up more than 75% of the space, it might just be really, really small.

Here is a nice animation to demonstrate what I'm doing here:

Eventually, it becomes this, in which the points are barely moving. This is when I see what nails it is touching:

Here is the ungolfed, animation code:

```
import java.awt.Color;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class Q extends JPanel{
    List<Point>points=new ArrayList<Point>();
    List<Point>n=new ArrayList<Point>();
    public Q() throws InterruptedException{
        double[][]rawPoints={{0, 0}, {2, -1}, {3/2, 4/3}, {7/2, 1/3}, {11/2, 16/3}, {1, 16/3}, {0, 1}, {7, -2}, {3, 4}, {8, 1}, {3, -1}, {11, 0}};
        double[][]rawNails={{1, 1}, {3, 1}, {4, 4}, {1, 3}, {2, 2}, {5, -1}, {5, 0}, {6, 2}, {7, 1}, {6, 0}};
        List<Point>p=new ArrayList<Point>(),nails = new ArrayList<Point>();
        double factor = 50;
        for(double[]rawP:rawPoints){p.add(new Point(rawP[0]*factor+100,rawP[1]*factor+100));}
        for(double[]rawN:rawNails){nails.add(new Point(rawN[0]*factor+100,rawN[1]*factor+100));}
        n=nails;
        JFrame frame=new JFrame();
        frame.setSize(700,500);
        frame.setVisible(true);
        frame.getContentPane().add(this);
        d(p,nails);
    }
    public static void main(String[]a) throws InterruptedException{
        new Q();
    }
    void d(List<Point>a,List<Point>nails) throws InterruptedException{
        //add midpoint every iteration until length of 1 is achieved
        //begin algorithm
        //stop points that are within a small amount of a nail
        double distance=20;
        while(distance>1){
            distance=0;
            for (int i=0;i<a.size()-1;i+=2){
                double fir=a.get(i).x;
                double sec=a.get(i).y;
                double c=(fir+a.get(i+1).x)/2;
                double d=(sec+a.get(i+1).y)/2;
                a.add(i+1,new Point(c,d));
                double dist=distBP(new Point(fir,sec),new Point(c,d));
                if(dist>distance){distance=dist;}
            }
        }
        for(Point p:a){a.set(a.indexOf(p), new Point(p.x,p.y));}
        //algorithm starts here:
        setEqual(a);
        repaint();
        invalidate();
        System.out.println(a);
        int count=0;
        while(true){
            count++;
            for(int index=0;index<a.size()-2;index++){
                double x2=(a.get(index).x+a.get(index+2).x)/2;
                double y2=(a.get(index).y+a.get(index+2).y)/2;
                int pointStable=0;
                if(distBP(a.get(index),a.get(index+1))<.5){a.remove(index);}
                for(Point n:nails){
                    if(distBP(n,new Point(x2,y2))<1){pointStable=1;}
                }
                if(pointStable==0){a.set(index+1, new Point(x2,y2));}
            }
            if(count%10==0){
            setEqual(a);
            invalidate();
            repaint();
            Thread.sleep(5);
            }
        }
        //System.out.println(a);
    }
    void setEqual(List<Point>a){
        points = new ArrayList<Point>();
        for(Point p:a){points.add(p);}
    }
    double distBP(Point a,Point b){
        return Math.sqrt(Math.pow(b.x-a.x, 2)+Math.pow(b.y-a.y, 2));
    }
    @Override
    public void paintComponent(Graphics g){
        g.setColor(Color.white);
        g.fillRect(0,0,getWidth(),getHeight());
        g.setColor(Color.black);
        for(Point p:points){
            g.drawRect((int)p.x, (int)p.y, 1, 1);
        }
        for(Point nail:n){
            g.drawOval((int)nail.x-2, (int)nail.y-2, 4, 4);
        }
    }
}

```

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


# Question
Title: Write a line in program that looks useless
Write some program (the size doesn't matter), and put a line that looks useless, but it's actually not - if it would be removed, the program would crash, or do something wrong. Feel free to mark the line that looks unused by a comment, or mention it your code description, like in example below (of course, in this example, the line is actually not needed, it's just an example).

```
int main(void) {
    /* The line below is actually needed. */
    2 + 2;

    return 0;
}

```

As this is popularity contest, the solution with highest number of votes wins.

# Answer
> 34 votes
## C

```
int main(int argc, char **argv) {
    switch(argc) {
        case 2:
            ;
            int allowed = 0;
        case 3:
            argc--;
            break;
        default:
            argc = 3;
    }
    return 0;
}

```

Won't compile if we remove the single `;`.

**EDIT**:

Solution below:

> This happens because a `case` statement is just a label, and, as such, must be followed by a statement (which the standard refers to as a "specifier for actions to be performed", which rules out declarations). To prevent this, we prefix the declaration with a `;`, a *null statement*. Specifications for the `case` label can be found here at page 142 (131 in-document)

# Answer
> 23 votes
## C / C++

Just some code written in the style of introduction / tutorial...

**Tutorial nr. 2**: reading in numbers, performing mathematical operations on them, and printing the results.

```
//////////////////////////////////////////////////
///////////////////////////////////////////////////
/////                                            //
/////           T  U  T  O  R  I  A  L           //
/////                                            //
///////////////////////////////////////////////////

#include "stdio.h"

int main()
{
    ///////////////////////////////////////////////
    // Local variables (int means integer!!)      /
    int a, b, result;

    ///////////////////////////////////////////////
    // Reading them in                            /
    scanf("%d", &a);
    scanf("%d", &b);

    ///////////////////////////////////////////////
    // Performing an operation, e.g. addition!!!  /
    result = a+b;

    ///////////////////////////////////////////////
    // Why is the next line absolutely mandatory??/
    result = 42;
    printf("The result is: %d", result);

}

```

Removing the line `result = 42;` which at first glance looks both superfluous, and, considering the stated objective, actually wrong, will actually cause the program to not do what the description states.

Why?

> Trigraphs strike again! *??/* will be replaced by the preprocessor with *\*, which will, in turn, concatenate the next line into the comment. The *result = 42;* becomes part of the comment, so it "saves" the printing line. With the *result = 42;* line removed, the *printf* line will be swallowed by the comment. Some compilers might give a warning, or trigraphs might be turned off as default and must be turned on for this example to work. Syntax highlighting might also betray it, but there are compilers and IDEs around which leave you none the wiser.

# Answer
> 19 votes
# Whitespace

Unfortunately I cannot show my program here because StackExchange strips all trailing whitespace. The same is true of pastebin.com and pastie.org, so I can’t link to it either.

Of course, the **entire program** “looks useless”, but if you remove any line, it will do something different.

# Answer
> 9 votes
# JavaScript:

```
for (var a = 0, b = 4; ++a < b; a++)b+-

2 + 2; // This line is needed, or it will alert twice!
alert(a);

```

> The reason it works is because the body of the `for` is `b+-`, not `b++` or `b--`; therefore, if you remove the required line, it will add to `b` the value of `-alert(a)`.

# Answer
> 8 votes
# C:

```
#include <stdio.h>
#include <string.h>

int main() {
    int i,sum;
    char s[4];

    /* Add all the integers < 1000 that contain no '0' or '9' */
    sum=0;
    for (i=0; i<1000; i++) {
        sprintf(s,"%d",i);
        if (strchr(s,'0')) goto skip;
        if (strchr(s,'9')) goto skip;
        sum += i;
      skip:
        i = i; /* Don't delete this line! */
    }
    printf("The answer is %d\n",sum);  /* <<< Should be 258948 */
    return 0;
}

```

If you delete the line `i = i;` then the code won't work. This is because...

> ... in fact it won't even compile. According to the C standard, labels like *skip* in the above example **must** be associated with a statement. Even a single semicolon would have sufficed, but if you delete the whole line then the label has no associated statement and compilation fails. This answer explains in a bit more detail.

# Answer
> 7 votes
## APL

Here's an APL function:

```
i_←{
  ⍺←⎕IO ⋄ ⎕IO←⍺
  ⍵⍴⍳×/⍵
}

```

It does the same thing as J's monadic `i.`:

```
      i_ 5 5
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

```

It can take an optional left argument that gives the offset:

```
      0 i_ 5 5
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

```

The line `⍺←⎕IO ⋄ ⎕IO←⍺` looks useless ("assign `⎕IO` to , then assign  to `⎕IO`"), but the first part only runs if no left argument is given, so in fact it does do something:

* if no  is given, set  to (global) `⎕IO`.
* set (local) `⎕IO` to

# Answer
> 7 votes
## C#

```
Func<int, int> fibo;
fibo = null; //Note that this can be set to *any* Func<int, int> reference.  It doesn't matter.
fibo = x => x < 1 ? 1 : fibo(x-1) + fibo(x-2);

```

The variable `fibo` must be assigned before you can use it inside a lambda, even if you’re assigning that lambda to `fibo` itself. If you remove the (seemingly useless) assignment, a compiler error will occur (“Use of unassigned local variable 'fibo'”).

# Answer
> 5 votes
Windows Batch:

```
echo hello
pause
echo world

```

Set the program running and modify the file to:

```
rem test01
pause
echo hello world

```

If you remove or resize the comment, it will cause havoc as the 1st instance of the program pauses and then continues interpreting from the 19th byte onwards.

# Answer
> 4 votes
**COBOL** (IBM Mainframe)

```
   ID DIVISION.
   PROGRAM-ID. USELESS.
   DATA DIVISION.
   WORKING-STORAGE SECTION.
   01  W-WHEN-COMPILED              PIC X(8)BX(8) VALUE SPACE.
   PROCEDURE DIVISION.
       IF W-WHEN-COMPILED EQUAL TO SPACE
           NEXT SENTENCE
       END-IF
       MOVE SPACE                   TO W-WHEN-COMPILED.
       MOVE WHEN-COMPILED           TO W-WHEN-COMPILED

       DISPLAY W-WHEN-COMPILED " HELLO WORLD!"
       GOBACK
       .

```

If you run the above program (any IBM Mainframe COBOL since COBOL II (first IBM compiler to 1985 standard, probably other IBM COBOLs as well) the output is:

> 02/22/14 13.11.02 HELLO WORLD!

However, if you remove the triply-useless line "MOVE SPACE TO W-WHEN-COMPILED." (the field has an initial value of space, and has other content placed in it in the next instruction, and it is branched over anyway) the program produces no output and actually Abends (U4038) (that means it crashes) with the following message:

```
 IGZ0037S The flow of control in program USELESS proceeded beyond the
          last line of the program.  From compile unit USELESS at entry
          point USELESS at compile unit offset +000003AC at entry offset
          +000003AC at address 119003AC.

```

(message code and text would vary amongst compilers, offsets depend upon actual compiler used and compile options, address depends on where program is loaded when EXECuted).

The reason is the `NEXT SENTENCE`. This is a `Secret GO TO`. The compiler hunts down the next full-stop/period in the source, and generates a branch to the following instruction. From COBOL II, the use of full-stops/periods was relaxed. A program must end with a full-stop/period. In this case, the branch is off the end of the program.

Both programs compile 100% clean (no diagnostic messages, Return Code of zero).

This behaviour is a dumb "IBM Extension" to COBOL. The 1985 Standard does not allow `NEXT SENTENCE` within `IF`/`END-IF` (`CONTINUE` is used instead, which is a no-op). IBM allowed it - causing horrible Gotchas from time-to-time.

# Answer
> 4 votes
**JAVASCRIPT**

```
var a = function(b) {
    return b;
}

; // This must be here

(function() {
    // more code
}());

```

Without the semicolon then `a` would become what ever the return value from 2nd function is - in this case it's `undefined`. Because the function originally assigned to `a` will be executed right away with the second function as the argument `b`.

# Answer
> 4 votes
# Java

```
package stackexchange;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.HttpURLConnection;
import java.net.URL;

public class Curl
{
    public void getUrl(String address)
    {
        try {
            URL url = new URL(address);
            HttpURLConnection conn = (HttpURLConnection) url.openConnection();
            conn.setRequestMethod("GET");
            BufferedReader input = new BufferedReader(new InputStreamReader(conn.getInputStream()));

            /* don't remove this line! */
            http://codegolf.stackexchange.com

            while( true ){
                String line = input.readLine();
                if( line==null ) break http;
                System.out.println(line);
            }

            input.close();

        } catch(IOException ex){
            // ignore.
        }
    }

    public static void main(String[] args) {
        Curl curl = new Curl();
        curl.getUrl("http://codegolf.stackexchange.com");
    }
}

```

It is a working program that retrieves a web page from an URL. You might be surprised that the line

```
            http://codegolf.stackexchange.com

```

compiles without even a warning. In fact, the program doesn't compile without it.

> It is actually a label, `http:`, followed by a comment, `//codegolf...`. The label applies to the while and is used in the `break http;` statement.

# Answer
> 3 votes
## Ruby

```
require 'prime'

# Given a regular expression, return the smallest prime containing it
# and the substring of the prime that matches it
def smallest_prime_matching_regexp(regexp)
  match = 'this assignment is necessary even though the value is never used'
  prime = Prime.find { |n| match = n.to_s[regexp] }
  return prime, match
end

[ /4/, /1+2/, /[02468]{2,}/ ].each do |regexp|
  prime, match = smallest_prime_matching_regexp(regexp)
  puts "#{regexp.inspect}:\t#{prime} (#{match})"
end

```

A similar thing came up at work recently--a coworker actually flagged my seemingly unnecessary initialization during code review, and I was really tempted to put the explanation inside a spoiler block. So I'll do that here.

> The line is necessary because a variable initialized inside a block is local to that block. If we initialize it outside the block, then the value is able to escape to the method scope.

Output as is:

```
/4/:    41 (4)
/1+2/:  127 (12)
/[02468]{2,}/:  223 (22)

```

Output with the first line of the method removed:

> undefined local variable or method \`match' for main:Object (NameError)

# Answer
> 3 votes
## PHP

```
<?php
$some_html_text= <<<EOT
<h1>This is a Header </h1>
<body> This is a body </body>
EOT;
//This is a comment

```

Here, `\n//This is a comment` is necessary. Without it the code won't run.

At least a `\n` char is necessary after `EOT;` to run it properly

# Answer
> 3 votes
```
#include <stdio.h>
#include <stdlib.h>

void strcmp_or_die(char *s, char *t) {
    if(!strcmp(s, t)) {
        printf("Success!\n");
    } else {
        int *ptr = NULL;
        *ptr = 0;
    }
}

int main(void) {
    char blah = '\0'; //segfaults without this line

    char v[2] = "ok";
    strcmp_or_die(v, "ok");
}

```

> Simple string overflow problem.

# Answer
> 2 votes
# ~-~!

This is probably the stupidest, most obvious one here.

```
'=|hello\|:
'=~!|Useless?\|:
@'[|y|]|n|:

```

It throws an error without that second line, with it it prints `y`.

> the backslash isn't an escape character, hehe.

# Answer
> 1 votes
# Windows Batch

This is a batch file that prints the numbers 1 to 10 with an empty line after each:

```
@echo off

setlocal EnableDelayedExpansion

set NL=^

rem Previous two lines deliberately left blank for NL to work.

for /l %%a in (1,1,10) do (
    echo %%a!NL!
)

endlocal

pause

```

This effectively makes use of a dirty hack to store a newline inside a variable (the use of delayed expansions gets rid of the more scary looking NL line in the linked answer). If you remove or otherwise change the two completely useless-looking blank lines above the comment, well, it won't work.

# Answer
> 1 votes
# troff

Troff is the most wonderful text processing system. I use it for my documents. It requires a macro system in order to be ready to be used, and the most famous is the `ms` macro package. Let's compile the following piece of code with the classical `-ms` option.

```
.\" -ms macro package
.\" the following line seems to be useless
\& \" print an invisible character
.ad c
.sp |300p \" absolute vertical positionning
.ps 36p
.ft B
My title.
.PP
This is a paragraph.

```

The third line seems to be useless, and would actually be useless without the macro package. Since it is followed two lines below by an absolute vertical positionning, it could seem meaningless to print nothing before. But without this invisible character, the vertical positionning will have no effect, though I am not absolutely sure I could explain why (see this thread if you want to have a glance at the discussion). This makes the new user crazy, but then the trick should become familiar to the more experimented user.

Just checked with my favorite version of troff which is not very known (heirloom troff), but I am pretty sure it still works the same with GNU troff.

---
Tags: popularity-contest, underhanded
---


title: Stabilize a Brick Structure

text:
# Question
Title: Stabilize a Brick Structure
# Bricks and Stability Defined

*This question uses the same definition of bricks and stability as Is the brick structure stable?*

Let `[__]` represent a masonry brick and

```
         .
         .
         .
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK? . . .
  BRK?BRK?BRK?BRK?
BRK?BRK?BRK?BRK?BRK?

```

represent an arbitrary arrangement or *structure* of these bricks, with every other row offset by half a brick, as is usual in brick construction. The structure can extend up and to the right indefinitely, but the string representation will always be a perfectly rectangular text block (having trailing spaces where necessary) whose width is divisible by 4.

Each `BRK?` in the structure may either be a brick (`[__]`) or empty space (4 spaces).

For example, one possible (unstable - read on) structure is

```
[__]    [__]    [__]
  [__]        [__]
[__][__]    [__]

```

A structure's stability is important, and a structure is only stable if every single one of its bricks is stable.

There are three ways an individual brick may be stable:

1. Any brick on the ground (the lowest line of bricks) is stable.
2. Any brick that has two bricks directly below it is stable:

```
  [__]   <- this brick is stable
[__][__] <- because these bricks hold it up

```
3. Any brick that has a brick both above and below it on the same side is stable:

```
  [__]  [__]
[__]      [__] <- these middle bricks are stable
  [__]  [__]      because the upper and lower bricks clamp them in

[__]          [__]
  [__]      [__]   <- these middle bricks are NOT stable
    [__]  [__]

```

(Yes, I know these rules aren't physically accurate.)

The last challenge was about determining *if* a structure was stable. This one is about stabilizing those that aren't.

# Challenge

Write a program that takes in a potentially unstable arrangement of bricks and adds new bricks into empty brick spaces to make everything stable, printing the result. This is to be done without increasing the overall dimensions of the input text block.

The goal is to create an algorithm that makes the structure stable by adding as few bricks as possible.

This JSFiddle (source) lets you generate random arrangements of bricks for use while testing your program. (Wish I could stack snippets instead.) `Width` is the number of bricks on the base layer, `Height` is the number of brick layers, and `Density` is the fraction of filled brick spaces.

For example, with `Width = 5, Height = 3, Density = 0.6` a possible output is

```
....[__]....[__]....
..[__]....[__]......
[__]............[__]

```

A way to stabilize this with 4 new bricks is

```
....[__]....[__]....
..[__][__][__][__]..
[__][__]....[__][__]

```

Your program must be able to stabilize any brick structure the JSFiddle can generate.

* This includes the empty string (which is considered stable).
* The brick will always be `[__]`. Periods (`.`) are only used for clarity. Your program may use periods or spaces for empty space.
* The structure may already be stable, in which case nothing needs to be done (besides printing it).
* The JSFiddle always generates structures that can be stabilized (by avoiding `Width = 1` and bricks in the top corners). You can rely on this. (Filling all but the top corners is sure to stabilize things but this is clearly not optimal.)
* Assume no invalid input. Take input as string however you like. Print the stabilized structure to stdout or similar.
* Remember that the text block dimensions should not change size.
* Preexisting bricks cannot be moved or removed. Placement of new bricks must follow the offset-every-other-row grid pattern. All bricks must be completely in bounds.
* It is encouraged (but not required) that you print the preexisting bricks as `[XX]` instead of `[__]`, so people can better see how your solution works.

# Scoring

At the bottom of the JSFiddle are 8 predefined unstable brick arrangements. (They use `[__]` and `.` and should stay that way unless you're using `[XX]` and/or  instead.) Some are random and some I created myself. To calculate your score, run your program on each of them in turn and sum the number of **new** bricks added to each.

The less new bricks you've added the better. The submission with the lowest score wins. In case of ties the oldest answer wins.

If things get contentious I may add a few more predefined cases and judge the winner based on them.

# Further Notes

* Your program needs to run on the order of minutes on a modern computer for brick grid width and height less than 100. (Max 10 minutes on a computer like this.)
* You may not hardcode your output for the 8 predefined structures. Your program must treat them as it would treat any other arrangement.
* Please include an example output or two, or any interesting structures you'd like to share. :)
* This problem is somewhat related to finding a minimum spanning tree.

# Answer
> 3 votes
# Java - 5,056 bricks

* 20x20, 0.03 - **75**
* 15x81, 0.05 - **431**
* 50x50, 0.20 - **882**
* 99x99, 0.01 - **2,567**
* Plain Pedestal - **269**
* Simple House - **129**
* Criss-Cross Tower - **323**
* Bridge Beginnings - **380**

Source code is viewable here.

The code runs in a few milliseconds for any of the 8 scoring inputs. There are some noticeably suboptimal outputs, particularly in the criss-cross tower and 99x99 cases. I have several ideas on how to improve the routine, but it's fairly bulky as-is, and hence I'll let it alone for now.

The outputs massacre the laws of physics to a comedic extent. :D

Some samples are shown below.

### 20x20, 0.03 Output

```
................................................................................
..........[XX]..................................................................
........[  ][  ]................................................................
..........[  ]..................................................................
............[  ]................................................................
..........[  ]..................................................................
............[  ]....................[XX]........................................
..........[  ]....................[  ][  ]......................................
....[XX]....[  ]....................[  ]........................................
..[  ][  ][  ][  ]................[  ]..........................................
....[XX]....[  ][XX]................[  ]........................................
..[  ]........[  ]................[XX]..........................................
....[  ]........[  ]............[  ][  ]........................................
..[  ]........[  ]................[  ]..........................................
....[  ]........[  ]............[XX]................................[XX]........
..[  ]........[  ]....[XX]........[  ]................[XX]........[  ][XX][  ]..
....[  ]........[  ][  ][  ]....[  ]....[XX]........[  ][  ]........[  ][  ][XX]
..[  ][  ]....[  ]....[  ]........[XX][  ][  ]........[  ]........[  ]....[  ]..
....[  ]........[  ]....[  ]....[  ]....[  ]............[  ]........[  ]....[  ]
......[XX]....[  ]....[  ]........[  ][  ]............[  ]........[  ]....[  ]..
....[  ]........[  ]....[  ]....[  ]....[  ]....[XX]....[  ]........[  ]....[  ]

```

### Simple House Output

```
................................................................................
................................................................................
................................................................................
......................................[XX]......................................
....................................[XX][XX]....................................
..................................[XX][  ][XX]..................................
................................[XX][  ][  ][XX]................................
..............................[XX][  ]....[  ][XX]..............................
............................[XX][  ]........[  ][XX]............................
..........................[XX][  ]............[  ][XX]..........................
........................[XX][  ]................[  ][XX]........................
......................[XX][  ]....................[  ][XX]......................
....................[XX][  ]........................[  ][XX]....................
..................[XX][  ]............................[  ][XX]..................
................[XX][  ]................................[  ][XX]................
..............[XX][  ]....................................[  ][XX]..............
............[XX][  ]........................................[  ][XX]............
..........[XX][  ]............................................[  ][XX]..........
........[XX][  ]................................................[  ][XX]........
......[XX][  ]................................................[  ][  ][XX]......
....[XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX]....
......[XX][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ][  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ][  ]........[XX]....
......[XX]....[XX][XX][XX][XX][  ]....[XX][XX][XX][XX][XX][XX]........[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ]............[XX]....
......[XX]....[XX]....[  ][XX]........[XX]....[  ]....[  ][XX]........[XX]......
....[XX]....[  ]....[  ][  ][  ]....[  ]....[  ]........[  ]............[XX]....
......[XX]....[XX]....[  ][XX]........[XX]....[  ]........[XX]........[XX]......
....[XX]....[  ]........[XX]........[  ]....[  ]........[  ]............[XX]....
......[XX]....[XX]........[XX]........[XX][XX][XX][XX][XX][XX]........[XX]......
....[XX]....[  ]........[  ]........[  ]....[  ][  ][  ][  ]............[XX]....
......[XX]....[XX]........[XX]........[  ]....[  ]....[  ]............[XX]......
....[XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX]....

```

# Answer
> 2 votes
# Python, 18992

This is the most simplistic solution and the worst score possible. It's only for reference; the thing to beat. It fills every empty space except the two top corners with bricks, guaranteeing stability.

```
s = '''
....[__]....[__]....
..[__]....[__]......
[__]............[__]
'''

def brickify(structure):
    structure = filter(lambda x: x, s.replace('__', 'XX').split('\n'))
    if not structure:
        return '', 0
    if len(structure) > 1 and len(structure) % 2:
        structure[0] = '----' + structure[0][4:-4] + '----'
    added = 0
    offset = False
    for i in range(len(structure)-1,-1,-1):
        line = structure[i]
        if offset:
            line = line[2:-2]
        added += line.count('....')
        line = line.replace('....', '[__]')
        if offset:
            line = '..' + line + '..'
        structure[i] = line
        offset = not offset
    structure[0] = structure[0].replace('----', '....')
    return structure, added

s, a = brickify(s)

#print '\nNew bricks:', a

for line in s:
    print line

```

To use copy the initial structure into the triple quotes at the top of the program.

Here it is run on the house, adding 609 bricks:

```
..[__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][__][__][XX][__][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][__][XX][XX][__][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][__][XX][__][XX][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][XX][__][__][XX][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][XX][__][__][__][XX][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][XX][__][__][__][__][XX][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][XX][__][__][__][__][__][XX][__][__][__][__][__][__]..
[__][__][__][__][__][__][XX][__][__][__][__][__][__][XX][__][__][__][__][__][__]
..[__][__][__][__][__][XX][__][__][__][__][__][__][__][XX][__][__][__][__][__]..
[__][__][__][__][__][XX][__][__][__][__][__][__][__][__][XX][__][__][__][__][__]
..[__][__][__][__][XX][__][__][__][__][__][__][__][__][__][XX][__][__][__][__]..
[__][__][__][__][XX][__][__][__][__][__][__][__][__][__][__][XX][__][__][__][__]
..[__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][XX][__][__][__]..
[__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__][__]
..[__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__]..
[__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][XX][XX][XX][__][__][XX][XX][XX][XX][XX][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][__][__][__][__][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][__][__][__][__][XX][__][__][XX][__]..
[__][XX][__][__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][XX][XX][XX][XX][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][__]

```

The number of bricks it adds for each of the 8 predefined structures in order are

```
374 1107 2041 9627 506 609 1088 3640 (sum to 18992)

```

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


# Question
Title: Prolific Perfect Pangram Programs Pertaining to Printable ASCII
**Updates: Time limit removed. You must be able to describe output - see new rule.**

A pangram is a sentence that uses every letter in the alphabet at least once, such as:

> *The quick brown fox jumps over the lazy dog.*

A *perfect* pangram uses every letter exactly once.

Consider writing a program that is a perfect pangram, using the 95 printable ASCII characters (hex codes 20 to 7E) as the alphabet:

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

Such a program must contain exactly 95 characters, with each printable ASCII character occurring exactly once, but in any order. (Thus there are 95! = 1.03×10148 possibilities.)

Your task is to write this program such that the number of printable ASCII characters printed to stdout is as high as possible (i.e. prolific).

Your score is the number of printable ASCII characters your program outputs **(the *total* amount, not the *distinct* amount: `AABC` scores 4 whereas `ABC` scores 3)**. The highest score wins.

# Details

* The output may contain any characters (including duplicates) but only instances of the 95 printable ASCII characters count towards your score.
    + You can use this JSFiddle to count the number of printable ASCII characters in any string.
* If your language does not have stdout use the most appropriate alternative.
* Your program...
    + must have finite runtime **(the time limit has been removed)**
    + must have finite output
    + may contain comments
    + must compile and run without (uncaught) errors
    + must not prompt for or require input
    + must be time invariant and deterministic
    + must not use external libraries
    + must not require a network connection
    + must not make use of external files
        - (you may use the program file itself as long as changing the file name does not alter the program's behavior)
* If this task is impossible is some language that's just too bad.
* You must give your exact output **or precisely describe it if it is too large to fit in a post**. You do not actually have to run your program. As long as it *would* run in a finite amount of time on a computer with an unbounded amount of memory it is valid.

# Example

This simplistic Python 2 program is a possible solution:

```
print 9876543210#!"$%&'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghjklmoqsuvwxyz{|}~

```

It outputs `9876543210` which contains 10 printable ASCII characters, thus scoring 10.

# Answer
# GolfScript, over 2↑↑↑(9871↑↑2) chars

```
2 9871.?,{;0$[45)63]n+*~}/
#!"%&'(-:<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ\^_`abcdefghijklmopqrstuvwxyz|

```

Prints an integer. Take advantage of unlimited CPU register size (which determines the maximum string length in Ruby), memory and run time. The linefeed is solely for readability.

### The code

```
2             # Push 2.
9871.?        # Push b := 9871↑↑2 = 9871↑9871 = 9871**9871.
,{            # For each i from 0 to b - 1:
  ;0$         #   Discard i and duplicate the integer on the stack.
  [45)63]n+*  #   Replicate ".?\n" that many times.
  ~           #   Evaluate.
 }/           #

```

### The score

Define **b = 9871↑↑2** (see Knuth's up-arrow notation).

* **.?** executes **f : x ↦ x↑x**.
* The inner block executes **g : x ↦ fx(x)**.

Since **f(x) = x↑x = x↑↑2**, **f2(x) = (x↑x)↑(x↑x) \> x↑x↑x = x↑↑3**,
**f3(x) = ((x↑x)↑(x↑x))↑((x↑x)↑(x↑x)) \> (x↑x↑x)↑(x↑x↑x) \> x↑x↑x↑x = x↑↑4** and so forth, we have
**g(x) \> x↑↑(x+1) \> x↑↑x**.
* The outer block executes **h : x ↦ gb(x)**.

Since **g(x) = x↑↑x = x↑↑↑2**, **g2(x) = (x↑↑x)↑↑(x↑↑x) \> x↑↑x↑↑x = x↑↑↑3**,
**g3(x) = ((x↑↑x)↑↑(x↑↑x))↑↑((x↑↑x)↑↑(x↑↑x)) \> (x↑↑x↑↑x)↑(x↑↑x↑↑x) \> x↑↑x↑↑x↑↑x = x↑↑↑4** and so forth, we have **h(x) \> x↑↑↑(b+1)**.
* We start with the integer **2** on the stack, so the code calculates **h(2) \> 2↑↑↑(b+1).**
* The score is the number of decimal digits of **h(2)**, which is **log(h(2)) + 1 \> log(2↑↑↑(b+1)) \> 2↑↑↑b**.

Thus, the score is larger than **2↑↑↑(9871↑↑2)**.

**2↑↑↑n** grows at a ridiculous pace as **n** gets larger. **2↑↑↑4 := 2↑↑2↑↑2↑↑2 = 2↑↑2↑↑4 = 2↑↑65536**, which is a right-associative power tower of **65536** copies of **2**:

Similarly, **2↑↑↑5 := 2↑↑(2↑↑↑4)**, which is a power tower of **2↑↑↑4** copies of **2**.

Now, the score isn't **2↑↑↑4** or **2↑↑↑5**, it's larger than **2↑↑↑b**, where **b \> 2 × 1039 428**. That's a big number...
> 12 votes

# Answer
# Perl, 70\*18446744073709551615\*10^987654320

```
say q{!"#%&'+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ\]^_`bcdfghijklmnoprtuvwz|}x(1e987654320*~$[)

```

Output:

```
!"#%&'+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ\]^_`bcdfghijklmnoprtuvwz|

```

repeated **18446744073709551615\*10^987654320** times.

`$[` is by default `0`, so `~$[` is equivalent to `18446744073709551615`.

As a side note, I ran out of memory trying to create the number `10^987654320`.

---

## Old Answer (7703703696):

```
say qw(!"#$%&'*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`bcdefghijklmnoprtuvz{|}~10)x98765432

```

Output is:

```
!"#$%&'*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`bcdefghijklmnoprtuvz{|}~10

```

repeated 98765432 times.

Note: Run all samples with `perl -Mbignum -E`
> 22 votes

# Answer
# Bash+coreutils, 151,888,888,888,888,905 (1.5\*10^17)

```
seq 9E15;#\!%*+,-./2346780:=@ABCDFGHIJKLMNOPQRSTUVWXYZ]^_abcdfghijklmnoprtuvwxyz~"'$&()?<>`{}|[

```

Outputs integers 1 to 9x1015, one per line. Takes a long time.

Why `9E15`? It turns out that GNU `seq` appears to use 64-bit floats (double) internally. The largest whole number we can represent with this type, before increment by one stops working due to lack of precision, is 253 or 9007199254740992. The closest we can get to this with exponential notation is 9E15 or 9000000000000000.

To calculate the score, I am using adding up all the numbers with a given number of digits and adding 9E15, because there is a newline between each number:

```
8000000000000001*16 + 900000000000000*15 + 90000000000000*14 + 9000000000000*13 + 900000000000*12 + 90000000000*11 + 9000000000*10 + 900000000*9 + 90000000*8 + 9000000*7 + 900000*6 + 90000*5 + 9000*4 + 900*3 + 90*2 + 9 + 9000000000000000

```

I could pipe this output through `od` for an extra order of magnitude or so, but that makes the score calculation much harder.

---

Pre-rule change answer:

# Bash+coreutils, 18,926,221,380

```
seq 1592346780;#\!%*+,-./:=@ABCDEFGHIJKLMNOPQRSTUVWXYZ]^_abcdfghijklmnoprtuvwxyz~"'$&()?<>`{}|[

```

Outputs 1 to 1592346780. On my mid 2012 macbook (which is not that far off the linked benchmark), this takes about 9m45s.

I couldn't resist optimizing it a bit more, even though its probably meaningless.

### Output:

```
$ time ./pangram.sh | wc
 1592346780 1592346780 18926221380

real    9m46.564s
user    11m7.419s
sys 0m10.974s
$

```
> 11 votes

# Answer
## GolfScript, ≈ 3\*10^(2\*10^7) i.e. ≈ 3x1020000000

```
 87 9654321?,`0${;.p}/#!"%&'()*+-9:<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnoqrstuvwxyz|~

```

**How it works**

```
87 9654321?                "Pushes 87^9654321 to stack";
           ,               "Pushes an array [0, 1, 2 ... (87^9654321) - 1] to stack";
            `              "Creates a string representation of the array like "[0 1 2...]";
             0$            "Copies the string";
               {;.p}/      "Print the string wrapped in quotes X times";
                     #...  "This is all comment";

```

Here `X` is the character count (length) of the string representation of the array `[0, 1, 2..,(87^9654321) - 1]` which will be like `[0 1 2 3 4 ... (87^9654321) - 1]`

~~I am trying to calculate `X` here so as to find my score. `(87^9654321) - 1` is roughly `10^(10^7.272415829713899)` with `18724742` decimal digits.~~

`X` is roughly `3*10^(2*10^7)` so `X*X` is also same only. Note that these values are on a very lower side as due to computation limitations of (even) wolframa, I was not able to compute `sum (floor(log10(x)) + 1) for x = 1 to (87^9654321 - 1)` which is the true value of `X`
> 6 votes

# Answer
# MATLAB, 95

Code

```
char(37-5:126)% !"#$&'*+,./0489;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`bdefgijklmnopqstuvwxyz{|}~

```

Output

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

Output contains all specified ASCII characters, each exactly once, and in order.
> 4 votes

# Answer
# Ruby, 89

```
p %q{!"#$&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnorstuvwxyz|~}

```

Output:

```
"!\"\#$&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnorstuvwxyz|~"

```

Contains all ASCII characters except, `p`, , `%`, `q`, `{`, and `}`.
> 2 votes

# Answer
# GolfScript, 93

```
{ !#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz|~}

```

Output:

```
{ !#$%&()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz|~}
}

```

Contains all ASCII characters except `"` and `'`.
> 2 votes

# Answer
# Golfscript - 27\*265439870

This my first Golfscript submission! :)

```
12,`{.+}6543 9870?*#!"$%&'()-/:;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz|~

```

Explanation:

```
12,                     - Creates an array of ascending numbers from 0 to 11
   `                    - Converts the array to a string
    {.+}                - Duplicates the string on the stack and concatenates the two
        6543 9870?      - Calculates 6543^9870 and pushes it to the stack
                  *     - Repeat the block 6543^9870 times
                   #... - The rest is a comment

```

The output is a load of lists of numbers. Consider the following code:

```
12,`{.+}1*

```

With `12,` it produces the following array:

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

```

The backtick turns that into a string, passing it to the block `{.+}`. This duplicates the string and then concatenates the two, producing:

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

```

The `1*` tells the interpreter to execute the previous block one time (21 = 2).

So, based upon that:

```
 12,`{.+}n*

```

Outputs the output of `12,`` 2n times.
> 2 votes

---
Tags: code-challenge, restricted-source, busy-beaver, pangram
---


title: Ray-trace a shiny sphere

text:
# Question
Title: Ray-trace a shiny sphere
I downloaded POV-ray and rendered this shiny metal sphere 90s style:

Your task is to do the same thing, but to do it by implementing the rendering engine yourself in as few bytes as possible. You don't have to replicate this exact image - any image of a reflective sphere above an infinite checkerboard will do, as long as it meets the criteria below.

Rules:

* The image must depict a reflective sphere hovering above an infinite checkerboard. Both the checkerboard itself and its reflection in the sphere must be shown in the image. It must be visually clear that this is what we're seeing. Beyond this, the details of the geometry, colours, material properties etc. are up to you.
* There must be some lighting in the scene: parts of the sphere should be darker than other parts, and visually it should be possible to tell roughly where the light is coming from. Beyond that, the details of the lighting model are up to you. (You can invent your own simplified lighting model if you like.) The sphere doesn't have to cast a shadow.
* The above two criteria - whether it really looks like a shiny sphere above a checkerboard illuminated by a light source - will be judged by the community using voting. Therefore, an answer must have a positive score in order to be eligible to win.
* The output must be at least 300x300 pixels. It can be displayed on the screen or written to a file, either is fine.
* Your code should run in less than an hour on a reasonable modern computer. (This is generous - POV-ray renders the above scene practically instantaneously.)
* No built-in ray tracing functionality may be used - you must implement the renderer yourself.
* This is , so the positive-scoring entry with the shortest code (in bytes) wins. However, you're also welcome to play the meta-game of getting the most votes by drawing a pretty picture (while keeping the code short of course).

This challenge might seem ridiculously hard, but since the geometry is fixed, the algorithm for rendering such a scene by ray tracing is pretty straightforward. It's really just a case of iterating over each pixel in the output image and evaluating a mathematical expression to see what colour it should be, so I'm optimistic that we'll see some good answers.

# Answer
## Python 2, 484 468 467 bytes

```
i=int;u=249.3
def Q(A,B):
 a=A*A+B*B+9e4;b=B*u+36e4;I=b*b-a*128e4
 if I>0:
    t=(-b+I**.5)/(5e2*a);F,G,H=A*t,B*t,u*t;J,K,M=F,G+.6,H+2.4;L=a**-.5;k=2*(A*J+B*K+u*M)*L;C,D,E=A*L-k*J,B*L-k*K,u*L-k*M;L=(C*C+D*D+E*E)**-.5;t=(-4e2-G)/D;return(D*D*L*L*u,((i(F+t*C)/200+i(H+t*E)/200)&1)*(u*D*L))[D>0]
 else:return(u*B*B/a,((i(-2e2/B*A)/200+i(-6e4/B)/100)&1)*u*B/a**.5)[B>0]
open("s.pgm","wb").write("P5 800 600 255 "+"".join(chr(i(Q(j%800-4e2,j/800-u)))for j in range(480000)))

```

Note: after `if I>0:` there is a newline followed by a single **tab** char before `t=`...

Running the program will create an 800x600 image named s.pgm

Started from a "real" ray tracer formulas (tweaked a bit for golfing).

Rendering takes about 3s on my dead old PC (0.7s with pypy).
> 29 votes

---
Tags: code-golf, graphical-output, 3d
---