text:
Circular shift an arbitrary byte-array bitwise
Given an arbitrary array of octets, and an offset measured in bits, the goal is to bitwise left rotate the array by the specified number of bit positions as if the entire array were a single contiguous number. Byte order is big-endian.
As an example, given the (not zero terminated) ASCII string abcd and a shift of 5 bits. we turn this array of bytes:
01100001 01100010 01100011 01100100

into this one:
00101100 01001100 01101100 10001100

Notice that the bits propagate to the left from byte to byte and that they wrap back around.
Now that I think you've all got the idea, the rules:

Your program should accept an arbitrary unsigned integer ("number of bits to shift" non-negative, possibly zero, limited only by the size of the standard integer type) and a raw stream of octets of arbitrary length (you may assume the length is strictly positive). How you accept these is up to you (file,stdin,parameter are all acceptable). Your program should output the shifted bytes in an analogous manner (i.e. file,stdout,return value).
"Cut-and-paste" style code is not allowed. That is, you can't rely on your user to set the value of a certain variable before calling your code.
The byte ordering is big-endian.
Shortest code wins.

EDIT: It's clear now I should have restricted the input output format a bit more. The solutions that are using ASCII 0s and 1s directly aren't very interesting unfortunately.

What's the range of valid input? Can the shift be negative? Zero? Greater than or equal to the number of bits in the array? Can the array be of length zero?

One of those questions is already answered, but I will clarify.

@PeterTaylor better?

Does it need to be a complete program?

I just want to ask why byte order matters?

@tia um... I am not certain it does. At the time I wrote it, it seemed like it did, but now I can't tell why. This idea came from something I was working on today, so it probably crept in from there.

@tia: Byte order matters for storing extended-precision integers in memory.  For example, an extended-precision library like http://gmplib.org/ stores the "limbs" in native-endian, so you can use word-sized shifts for shift-counts that aren't a multiple of 8 (in which case it's a memcpy with an offset).  To get the behaviour shown for the abcd char-array example, on a little-endian machine you can't load the whole thing as a 32-bit integer and rotate left by 5.  If you did that, bits coming out the top of a would go into b rather than wrapping around to d.

A C answer that treated the input as an int[] would work on big-endian implementations (and working on at least one implementation is enough for code-golf), but an x86 asm or machine-code answer would have to use byte shifts.

Has this ever been re-asked in a way that stops answers from doing input/output with each "bit" in a separate byte?  Totally agree that defeats the purpose of the question, since it just turns it into a memory-addressing problem.

Can we have some sample inputs/outputs? Like, (5, "abcd") should become...?

APL (1)
it's a builtin
      5⌽0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0
0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 1 0 0

C 89
Shifting is done in-place in *s array. l is array length and f is number of bits to shift.
void f(char*s,l,f){while(f--)for(int i=0,j,c=*s<0;s[j=i++]<<=1,s[j]+=i%l?s[i]<0:c,i<l;);}

C#, 321 308 304 bytes
var y=System.Text.Encoding.UTF8.GetBytes(args[1]).ToList();int i=int.Parse(args[0]),m,j=0;for(;i>7;y.RemoveAt(0),i-=8)y.Add(y[0]);byte c=0,u;for(m=8-i;j<y.Count;j++){u=(byte)((255<<m&y[j])>>m);if(j<1)c=u;y[j]<<=i;if(j>0)y[j-1]|=u;}y[^1]|=c;Console.Write(System.Text.Encoding.UTF8.GetString(y.ToArray()));

Dropped 13 bytes thanks to awesome suggestions from Kevin, and  another 4 bytes with suggestions from ceilingcat!
Uncompressed version below. This uses C# v9 top-level statements feature, so the program below compiles into an executable. Program expects two arguments: bits and bytes in a form of a UTF8 string (e.g., execute is as ./program 5 abcd).
// get bytes from the provided provided (assumed in UTF8)
var y = System.Text.Encoding.UTF8.GetBytes(args[1]).ToList();
int i = int.Parse(args[0]), m, j = 0; // i - how many bits to shift

// rotate full bytes first if bits >= 8
for (; i > 7; y.RemoveAt(0), i -= 8) // drop the first byte
    y.Add(y[0]); // append first byte to the end

byte c = 0, u; // c keeps the bits to wrap around from first byte to the last
               // u will be used to shift bits between neighboring bytes

// now i < 8 guaranteed
for (m = 8 - i; j < y.Count; j++)
{
    u = (byte) ((255 << m & y[j]) >> m); // bits to shift
    if (j < 1) c = u; // if we are on the first byte, store them in c
    y[j] <<= i; // shift the byte
    if (j > 0) y[j - 1] |= u; // shift the cutoff bits to prev byte
                              // if current byte is not the first byte
}

y[^1] |= c; // wrap around the bits

// and output
Console.Write(System.Text.Encoding.UTF8.GetString(y.ToArray()));

Welcome to Code Golf, and nice first answer! Be sure to check out our Tips for golfing in C# page for ways you can golf your program! You might want to add a TIO link or similar so others can test your code online.

@emanresuA Thanks! TIO's C# does not seem to support C#'s top-level statements and I couldn't find an online C# compiler that supports command line arguments...

while(i>7){y.Add(y[0]);y.RemoveAt(0);i-=8;} can be for(;i>7;y.RemoveAt(0),i-=8)y.Add(y[0]); for -3 and var i=int.Parse(args[0]) + var m=8-i;byte c=0,u;for(var j=0; can be int i=int.Parse(args[0]),m,j=0;byte c=0,u;for(m=8-1; for another -6. And if there isn't an online compiled for C# 9+, you could put the args in the header on TIO (and replace ^1 with y.Count-1, since TIO is below C# v8 apparently): try it online. Oh, and welcome to CGCC. :)

You can also golf the WriteLine to Write for another -4. (And apparently the Visual C# Online Compiler uses Args for the same behavior as args, so you could actually save an additional byte by using Visual C# Interactive Compiler as language and sacrificing ^1 to y.Count-1 to remove Console. for -1: try it online. But if you prefer to use standard C# with ^1 and top-level arguments I can understand.)

Thanks @ceilingcat for some great suggestions! Another 4 bytes off!

Thanks @KevinCruijssen ! 13 bytes are gone :) I am just starting golfing in C# (and in general) so all the advice is helping me a lot! I prefer to use standard C# :)

Sed, 35 bytes
:a
s/1-\(.\)\(.*\)/-\2\1/
ta
s/.//

Takes input on stdin, as number of bits to shift by in unary, followed by -, followed by the binary stream, without spaces. e.g.
echo 11111-01100001011000100110001101100100 | sed -f a.sed

outputs
00101100010011000110110010001100

Perl, 33 (32 + 1 for -p)
1while(s/1-(.)(.*)/-$2$1/);s/.//

Takes input on stdin, as number of bits to shift by in unary, followed by -, followed by the binary stream, without spaces. e.g.
echo 11111-01100001011000100110001101100100 | perl -pe '1while(s/1-(.)(.*)/-$2$1/);s/.//'

I can't find any rule you are breaking, although this isn't what I intended, since I didn't specify an encoding. Clever idea.

@Tim: I sort of took off from How you accept these is up to you, since the input was mostly unspecified. As an aside, this can take arbitrarily large shifts and bits. Also, taking the count in decimal would have made the sed version much longer.

APL (23)
{2⊥⍉(8,⍨⍴⍵)⍴⍺⌽,⍉⍵⊤⍨8/2}

This is a function that takes the rotation as its left argument and the byte array as its right argument (as numbers).
      5{2⊥⍉(8,⍨⍴⍵)⍴⍺⌽,⍉⍵⊤⍨8/2}97 98 99 100
44 76 108 140

C# (210)
void r(byte[] a, int n){string s="";for(int i=0;i<a.Length;i++)s+=Convert.ToString(a[i],2).PadLeft(8,'0');s=s.Substring(n)+s.Substring(0,n);for(int i=0;i<a.Length;i++)a[i]=Convert.ToByte(s.Substring(i*8,8),2);}

This is a function 'r' in C# that takes a byte[] and an integer n.
It does in-place rotation, so the original array is rotated, and nothing is returned.
I convert the byte array to string of bits, rotate, and convert back to bytes.
It seems like a cheat, but the requirements does not prevent it.
The pretty code is following:
void r(byte[] a, int n)
{
    string s = "";
    for (int i = 0; i < a.Length; i++)
        s += Convert.ToString(a[i], 2).PadLeft(8, '0');

    s = s.Substring(n) + s.Substring(0, n);

    for (int i = 0; i < a.Length; i++)
        a[i] = Convert.ToByte(s.Substring(i * 8, 8), 2);
}

As long as it works, you can do it however you want. Efficiency isn't required in code-golf.

C, 142 bytes
It's huge :(
Input is taken from parameters, puts shifted string to stdout.
main(int d,char**v){d=strtoul(v[1],0,10);while(d--){v[1]=v[2]+1;**v=*v[2];strcpy(v[2],v[1]);while(*(v[1]++));*v[1]--=0;*v[1]=**v;}puts(v[2]);}

q (18)
depending on how picky you are about exact output format and launch, i can get it down to 18 in q:
$ ls -l shift*.q
-rw-r--r-- 1 daviaaro ccM504 19 Jan  8 16:05 shift1.q
-rw-r--r-- 1 daviaaro ccM504 22 Jan  8 16:07 shift2.q
-rw-r--r-- 1 daviaaro ccM504 25 Jan  8 16:07 shift3.q
$ cat shift1.q
(rotate)."I*"$.z.x
$ q shift1.q 5 "01100001011000100110001101100100" <&-
"00101100010011000110110010001100"
$ cat shift2.q
-1(rotate)."I*"$.z.x;
$ q shift2.q 5 01100001011000100110001101100100 <&-
00101100010011000110110010001100
$ cat shift3.q
-1(rotate)."I*"$.z.x;
\\
$ q shift3.q -q 5 01100001011000100110001101100100
00101100010011000110110010001100
$

of course, it helps that the actual function happens to be in the standard lib :)
all three interpret two command-line args as int and string and rotate the string by the int
the first case just shows the string representation of the string (a (mostly) pasteable notation)
the second and third cases print it
in the first two cases, i'm relying on q to quit itself when run without stdin
the third case has an explicit quit command (and an extra command-line arg to suppress the REPL welcome message, which is automatically suppressed in the other cases due to stdin being closed)
note btw that the byte counts from ls include newlines, even on the two one-line files, and since q is fine with code files that are missing their last newline, the actual counts are 18, 21, and 24
ETA:
how do you feel about this?
$ q<<<'5 rotate 01100001011000100110001101100100b'
00101100010011000110110010001100b
$

is it valid? how would you count it? (the b is q's notation for a binary vector/bitstring. if you prefer, it would also work on the string version at the cost of an extra character)

The first one seems to break the requirement "Your program should output the shifted bytes in an analogous manner" in my opinion, since you accept input without quotes and return it with quotes. The second one seems to require the <&- on the commandline; that would have to be included in the character count.

And the -q flag counts as one extra character, so your counts from my point of view are: 21(but not valid), 24, and 25. Feel free to argue your case. Either of the second two answers are acceptable.

well, it sort of depends on the details. without the <&-, version two will still work, but the REPL will print a welcome banner and will remain open for interactive use after the program finishes. without the -q, version 3 will exit, but it will still print the welcome banner. if it matters, the welcome banner is printed to stderr, while the output is printed to stdout. would you consider any of those situations acceptable answers?

i'd like to note that the APL solution above doesn't seem to be getting charged for a newline . if we want to talk about solutions valid interactively rather than as code files, i have a full solution in six characters: rotate. :-p

Printing the banner to standard error is fine I guess. Keeping the REPL open is not. If I am keeping track then properly that means the last two solutions are both 24 then.

Regarding my first solution, note that it’s perfectly fine to invoke it with quotes around the bitstring—it has no particular effect on anything, since the shell will remove them, but it will make the input and output formats match. Does that change your stance on that one? Counting the <&-, it’s 21 characters.

Yeah. I thought of that already, I already decided to allow that as long as you suggested the idea.

ok, edited to reflect

Python, 43 42 bytes
Takes shifts and data from stdin, returns shifted data in stdout.
Input format is <shift_amount>\n<data>
a=-input();b=raw_input();print b[a:]+b[:a]

Can you please describe the input format, since I don't know the exact semantics of input and raw_input? I haven't used python in a while.

@Tim raw_input() fetches an input line from stdin (sys.stdin.readline()) and removes \n. input() does the same but eval()s input before returning. Input format is thus <shift_amount>\n<data>.

You've shifted bytewise.  Not bitwise.  Huge difference here.

Python 3, 40 Bytes
s,n=open(0);print(n[int(s):]+n[:int(s)])

Try It Online!
This is basically a port of Oberons answer, and takes the same input from stdin as his Python 2 solution:
in:
5
01100001011000100110001101100100
out:
00101100010011000110110010001100

this is also my first post on this site, happy to be here!

Welcome to the site.


text:
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

Which criterion is it? You can't have more than one.

Choosing some or none? Does the function sum all of the numbers, or a set?

You wrote check if it is possible to obtain a sum of S. What's S? Is that the array? If it's the array, then you can always obtain a sum from it, because you said that it's an array of integers.

@ProgramFOX: S is not the array; it's the value with which we are comparing the summed elements of the array (I thought the line you quoted was pretty clear on that, but I suppose not).

@KyleKanos ok, I see what he means now, I submitted an edit that should clear things up (if it's accepted)

@xfix, your edit takes a clear question and makes it confused.

This is the subset sum problem, but I think it's just about sufficiently different from the existing subset sum question to not count as a duplicate.

Well the examples certainly helped (I was halfway through a linear combination solution)

I think popularity contest is a bad fit for this question personally.

The explanation of example #3 should read "because no combination of the elements in the array can be added to produce 6", right?

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.

Instead of Permutations, maybe you could use power sets: Subsets[list] but that might only work if the list does not have duplicate values.

@Quincunx You are correct, using Subsets[list] is clearly better (and causes no problems with duplicate values); I will amend the code and my discussion accordingly.

Iterating through all subsets of set? Your approach will fail even for 50 elements array. Using Mathematica application for that sounds like sarcasm!

@SergeyS Why will it fail? 2**50 sets is too many sets for Mathematica?

@Quincunx - 2**50 is too large number of sets to iterate through. It will take years on personal computer.

@SergeyS Maybe it will take years, but who cares? It works (and even uses a mathematical operation (ie power set)).

If you're going for shortness you can save 4 more bytes: Subsets@list and Tr on a 1D list is the same as Total. You might be able to save another byte (but I'm not 100% sure), by replacing MemberQ with !FreeQ.

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];
}

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)

I appreciate the comments, but this style of leaving no space between code and comment is not too popular among me…

@manatwork better?

Much better. :)

Which version of Ruby? 1.9.2 protests against your style: “formal argument cannot be a constant”.

Also some typos: include? (no final “s”), extra “]” in the last subsetSum() call's parameters, either && instead of or, or put the expression in parenthesis. Beside that, seems that fails on example #4.

@manatwork 2.2dev
and I honestly was going to make it "n" and "s" for that reason, but OP wrote N and S...

Thanks for the information. Regarding the “#remove last number if it's over S” part, think to [-33,99] vs. 66. Better not remove list items greater than the sum.

@manatwork yeah that's true, didn't expect negative numbers

@manatwork even with all the updates, pry shows that it doesn't bother evaluating both sides of the ||, which is exceedingly strange. Why is it I always use development versions

Both || and or are short-circuiting. Use bitwise | (defined for booleans too) to ensure both terms are always evaluated. This isn't matter of version.

@manatwork did not know that. Unfortunately, that did not work either. I have a temporary solution (return true if ...) on two different lines, but it still occasionally short circuits (only on example 4), trying to solve...

Included additional method, which always works, but is less efficient.

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.

and this works...
I blame my ruby 2.2 dev version (well I have the less effective algorithm now...)

Good looking one liner: return s == 0 or l != [] and (f(l[1:], s) or f(l[1:], s - l[0]))

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)))))

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.

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)

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)

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

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 }));
    }
}

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

 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

I don't believe I've ever seen ungolfed APL before.

@Quincunx: well not on this site you wouldn't :)

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;
    }

}

Since this is a [tag:popularity-contest], there is no need to show golfed code. Instead, an explanation of how your program works would be better.

Oh... Sorry about that.

Fortran
Algorithm is as follows:

Check if the sum of the array is less than S
Check if any of the elements of the array equals S
Sort array
Slice linear elements of array & check if sum of slice is S
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

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)

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]))
}

Apparently I can't upvote his solution or comment on it, so I left an homage instead. ;)

You should be able to upvote; it comes at 15 rep. However, commenting everywhere comes at 50 rep.

@Quincunx I think it's because I'm not a registered user

The homage to the solution that uses my algorithm (for some reason broken on ruby 2.2dev). Or some fault of mine (it works fine on python though q-q)

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

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.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Regex for Finding Radioactive Elements
Find the shortest regex that matches all radioactive elements and nothing else in the Periodic Table of Elements.
Radioactive Elements
'Technetium','Promethium','Polonium','Astatine','Radon','Francium','Radium','Actinium','Thorium','Protactinium','Uranium','Neptunium','Plutonium','Americium','Curium','Berkelium','Californium','Einsteinium','Fermium','Mendelevium','Nobelium','Lawrencium','Rutherfordium','Dubnium','Seaborgium','Bohrium','Hassium','Meitnerium','Darmstadtium','Roentgenium','Copernicium','Ununtrium','Flerovium','Ununpentium','Livermorium','Ununseptium','Ununoctium'

Non-radioactive Elements
'Hydrogen','Helium','Lithium','Beryllium','Boron','Carbon','Nitrogen','Oxygen','Fluorine','Neon','Sodium','Magnesium','Aluminium','Silicon','Phosphorus','Sulphur','Chlorine','Argon','Potassium','Calcium','Scandium','Titanium','Vanadium','Chromium','Manganese','Iron','Cobalt','Nickel','Copper','Zinc','Gallium','Germanium','Arsenic','Selenium','Bromine','Krypton','Rubidium','Strontium','Yttrium','Zirconium','Niobium','Molybdenum','Ruthenium','Rhodium','Palladium','Silver','Cadmium','Indium','Tin','Antimony','Tellurium','Iodine','Xenon','Caesium','Barium','Lanthanum','Cerium','Praseodymium','Neodymium','Samarium','Europium','Gadolinium','Terbium','Dysprosium','Holmium','Erbium','Thulium','Ytterbium','Lutetium','Hafnium','Tantalum','Tungsten','Rhenium','Osmium','Iridium','Platinum','Gold','Mercury','Thallium','Lead','Bismuth'

Scored by character count in the regex.
Use standard Perl regex (just no specialized functions).
Assume all lower case.
You only need to count the characters of the regex itself.

Note if you used a program to get you started and maybe post how well it did. I'll post my best attempt as an answer to get started/show an example.

Can you quote a regex standard, such as POSIX regular, POSIX extended, PCRE…? Otherwise "language agnostic" doesn't really mean much.

Sorry, I have only had to use regex in java and javascript and don't really know all the differences. The goal is to create a regex that would work in most common languages without relying on language specific feature.

There is an ongoing discussion as to whether we want regex golf on this site. Please contribute.

@qw3n You could say “regular expression describing a regular language” to exclude all the language specific things.

Char count 59
e.+[hktv]|oh?r.+m|p...?o|r.*ci|be?.i|^c?u|rad|sta|has|ct|fe

Found via a mix of manually selecting good parts and running Peter Norvig's golfer on the remaining items.
Regex101 link

LOL accepted answer after over 2 years! Imagine that @drjimbob's answer was the previous accepted answer. 3 characters better than accepted answer!

For pete's sake! I've had the best answer for more than a year, and then I make it even better, and then you come along and do even better and get accepted!

Char Count 61
lon|ct|oh|^ra|...t.+i|^c?u|or.+u|r.+c.|e..+e|f.?e|^h?as|be*.i

One 3 characters better than accepted answer!
63-character solution found with Peter Norvig's Regex golf solver. 61-character improvement found by a personal rewrite of that program in Go.

Char count 64
^(c?u|ra|no)|e.[kht]|[^l][gecv]i|[^c]oh?[rn]iu|f.r|ac|sta|bn|has

Should note, used parts of qw3n solution to reduce down my solution.  Also used Peter Taylor's suggestion to trim two characters.

I have a feeling this is pretty near if not an optimal solution. Wish I'd seen that f.r part. :)

There's an easy 1-char saving by grouping everything anchored on ^, and another by changing ^(u|cu|...) into ^(c?u|...)

Char count 69
^u|e.[kht]|[^l][gecv]i|[^c]oh?[rn]iu|^cu|f[oe]|a[cds]t|has|nob|rad|du

Curium/Cerium are a pain to deal with

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Manipulate "RELATIVE" using 8 OP-codes
Rules:

Your program can be in any programming language.
Your program should not take any input.
Your program should transform the word "RELATIVE" into "STATIC". The word can at any stage only consist of uppercase letters A-Z.
Your program can only use 8 different operations.
The length, in number of letters, of the word cannot exceed 10 letters. If letters moves beyond that limit the letters will be deleted.
Your program must use all 8 operations before it can start reusing the operations again. All operations must be used the same amount of times.
The word must be "STATIC" at the end of the last chunk of 8 operations.
The very first OP used in the first chunk of OPs is never executed, so the program must output word "RELATIVE" of the first row.
The lines should be outputted in chunks of 8 lines, separated by a double linefeed between the chunks.
Your program should output the lines describing how it manipulates the string. Output each iteration of operations, one line for every applied operation in this form:

<iteration # in 6 numbers>: <operation> <current word after OP is executed>
The operations available:
INS     Move the current word 1 character to the right and
        replace first letter with 'A'.

DEL     Deletes the last letter in the word.

INC     Increase the second letter from the left with 1.
        Example: 'A' converts into 'B' or a 'Z' converts into 'A'.
        If the letter position is outside of the current word, nothing happens.

DEC     Decrease the fourth letter from the left with 4.
        Example: 'T' converts into 'P' or a 'C' converts into 'Y'.
        If the letter position is outside of the current word, nothing happens.

SWT     Swith letter number three from left with letter number two from right.
        If any of the letters are outside of current word, nothing happens.

INV     Invert the current word.

JMP     Invalidates the nextcoming OP.
        If this OP is used as OP #8 in a chunk, nothing happens.

REP     Execute the previous op again.
        If this OP is used as OP #1 in a chunk, nothing happens.

Example output (incomplete as the word is not "STATIC" at the end of the last chunk of 8 OPs):
000001: REP RELATIVE
000002: DEL RELATIV
000003: INS ARELATIV
000004: INC ASELATIV
000005: SWT ASILATEV
000006: INV VETALISA
000007: JMP VETALISA
000008: DEC VETALISA

000009: DEC VETWLISA
000010: JMP VETWLISA
000011: INS VETWLISA
000012: DEL VETWLIS
000013: REP VETWLI
000014: SWT VELWTI
000015: INC VFLWTI
000016: INV ITWLFV

The scoring is: (Sourcecode size in bytes) * (# OP-chunks). The program with the smallest score wins. The competition ends at 2014-12-31.

seriously… one year?

Yes, that end date was serious :)

We are allowed to hard-code values right?

Swith letter number three from left with letter number two from right. 0-based or 1-based numbering?

Yes, hard-coded values in sourcecode is okay, there is no limits for the actual sourcecode, you don't even have to have the actual word in memory anywhere, but the output must be correct. Numbering is 1-based. Letter #1 = first letter.

Is capitalization necessary?

Also, in regards to Rule 5: what happens to the A in INS? Is that replaced in case of the wrap, or is it ignored?

Capitalization is necessary, if you use INS on a 10 letter word then the last letter is replaced by the A

What would the REP in JMP DEC REP do?

It would repeat a JMP (unless the REP is used as OP #8 in a chunk)

How on Earth does the current wording of rule 5 support INS replacing the last letter of the word? Please rewrite the rule to be explicit and give examples.

Oh sorry, INS is supposed to be an insert before the word, as that is the only OP that can increase the word length I will rewrite rule #5 according to that logic.

GolfScript, 338 323 307 300 280 * 15 10 = 2800
{:x;.2$<)65-x+26%65+[]++\@>+}:d;
{[{}{4-4d}{);}{2 1d}{'A'\+}{-1%}{2$~}{....2<\[-2=]+\3>-2<+\[2=]+\-1>+}]=}:L;
1:i;
'RDLATIVE':&;
'"S<(hR\50%!iS[SA*v7qpq&={=kkkk."Y+iEpi5-]'{32-}%95base`8/
{1:j;0L.@{48-:^j*L@;.&\~:&;i'0'6*\+-6>': ''JDDIIIRSMEENNNEWPCLCSVPT'^>8%' '&n^0>:j;i):i;}%n@;@;}/

Newlines added for clarity only, and can be removed. Pretty sure the output is correct.
Test online
It probably can be golfed further.

I managed to chop off an entire 5 chunks of op-codes (although I did have to rewrite most of the algorithm).
Output:
000001: INC RELATIVE
000002: DEL RELATIV
000003: REP RELATI
000004: INS ARELATI
000005: DEC AREHATI
000006: INV ITAHERA
000007: JMP ITAHERA
000008: SWT ITAHERA

000009: DEC ITADERA
000010: INS AITADERA
000011: INV AREDATIA
000012: DEL AREDATI
000013: INC ASEDATI
000014: JMP ASEDATI
000015: SWT ASEDATI
000016: REP ASEDATI

000017: DEC ASEZATI
000018: INV ITAZESA
000019: DEL ITAZES
000020: SWT ITEZAS
000021: INS AITEZAS
000022: JMP AITEZAS
000023: INC AITEZAS
000024: REP AITEZAS

000025: DEC AITAZAS
000026: REP AITWZAS
000027: INS AAITWZAS
000028: INC ABITWZAS
000029: INV SAZWTIBA
000030: DEL SAZWTIB
000031: JMP SAZWTIB
000032: SWT SAZWTIB

000033: DEC SAZSTIB
000034: DEL SAZSTI
000035: INV ITSZAS
000036: SWT ITAZSS
000037: INS AITAZSS
000038: REP AAITAZSS
000039: JMP AAITAZSS
000040: INC AAITAZSS

000041: DEL AAITAZS
000042: INV SZATIAA
000043: INC SAATIAA
000044: REP SBATIAA
000045: INS ASBATIAA
000046: JMP ASBATIAA
000047: DEC ASBATIAA
000048: SWT ASAATIBA

000049: SWT ASBATIAA
000050: INS AASBATIAA
000051: INV AAITABSAA
000052: INC ABITABSAA
000053: DEL ABITABSA
000054: JMP ABITABSA
000055: DEC ABITABSA
000056: REP ABITABSA

000057: INV ASBATIBA
000058: DEL ASBATIB
000059: INS AASBATIB
000060: DEC AASXATIB
000061: JMP AASXATIB
000062: INC AASXATIB
000063: SWT AAIXATSB
000064: REP AASXATIB

000065: INV BITAXSAA
000066: DEL BITAXSA
000067: REP BITAXS
000068: SWT BIXATS
000069: INS ABIXATS
000070: INC ACIXATS
000071: JMP ACIXATS
000072: DEC ACIXATS

000073: INS AACIXATS
000074: INC ABCIXATS
000075: INV STAXICBA
000076: DEL STAXICB
000077: REP STAXIC
000078: JMP STAXIC
000079: SWT STAXIC
000080: DEC STATIC

Wow! I didn't expect any working solution so soon! Incredible


text:
Regex for Finding Non-Radioactive Elements
Find the shortest regex that matches all non-radioactive elements and nothing else in the Periodic Table of Elements. This is the inverse of Regex for Finding Radioactive Elements
Radioactive Elements
'Technetium','Promethium','Polonium','Astatine','Radon','Francium','Radium','Actinium','Thorium','Protactinium','Uranium','Neptunium','Plutonium','Americium','Curium','Berkelium','Californium','Einsteinium','Fermium','Mendelevium','Nobelium','Lawrencium','Rutherfordium','Dubnium','Seaborgium','Bohrium','Hassium','Meitnerium','Darmstadtium','Roentgenium','Copernicium','Ununtrium','Flerovium','Ununpentium','Livermorium','Ununseptium','Ununoctium'

Non-radioactive Elements
'Hydrogen','Helium','Lithium','Beryllium','Boron','Carbon','Nitrogen','Oxygen','Fluorine','Neon','Sodium','Magnesium','Aluminium','Silicon','Phosphorus','Sulphur','Chlorine','Argon','Potassium','Calcium','Scandium','Titanium','Vanadium','Chromium','Manganese','Iron','Cobalt','Nickel','Copper','Zinc','Gallium','Germanium','Arsenic','Selenium','Bromine','Krypton','Rubidium','Strontium','Yttrium','Zirconium','Niobium','Molybdenum','Ruthenium','Rhodium','Palladium','Silver','Cadmium','Indium','Tin','Antimony','Tellurium','Iodine','Xenon','Caesium','Barium','Lanthanum','Cerium','Praseodymium','Neodymium','Samarium','Europium','Gadolinium','Terbium','Dysprosium','Holmium','Erbium','Thulium','Ytterbium','Lutetium','Hafnium','Tantalum','Tungsten','Rhenium','Osmium','Iridium','Platinum','Gold','Mercury','Thallium','Lead','Bismuth'

Scored by character count in the regex.
Use standard Perl regex (just no specialized functions).
Assume all lower case.
You only need to count the characters of the regex itself.

Note if you used a program to get you started and maybe post how well it did. I'll post my best attempt as an answer to get started/show an example.
Edit:
Apparently Bismuth is radioactive, but since I'm assuming the universe would die from heat death before it was ever much of a problem I'm not going to worry about it now.

Nitpick: Bismuth is technically radioactive, although its decay rate is so vanishingly low that it can be treated as stable for all practical purposes.

@IlmariKaronen Interesting didn't know that. I copied the lists from the internet and you know how reliable that is ;).

I don't think the question is well specified. My understanding of "the shortest regex that matches all non-radioactive elements and nothing else" is that the string "y" shouldn't match since "y" isn't the name of a non-radioactive element; but both the solutions currently posted match "y"; effectively they do substring matches. My understanding of the question would be that the answer should be the shortest string representing a regular expression that is equivalent to the regular expression 'Hydrogen|Helium|...|Bismuth' (ie. the RE formed by joining the names of all non-radioactive elements w

In addition to your other question, I also ran this through Peter Norvig's Regex Golf solver, but it spat out a 99 character solution. Sometimes humans come out on top.

Small improvement on qw3n's solution (93 characters):
y|^v|h.[lfdn]|[^te]i[rodnts]|[lp].t[^o]|ru?[bs]|ll|^..ro|^[^r][^u].{1,4}$|ca..i|ma|s.l|tan|gs

Basically got rid of ^t[^eh] (7 characters) clause and replaced with tan|gs (6 characters).  Also I count qw3n's solution as 94 characters, not 95.

Character count 94
y|^v|h.[lfdn]|^t[^eh]|[^te]i[rodnts]|[lp].t[^o]|ru?[bs]|ll|^..ro|^[^r][^u].{1,4}$|ca..i|ma|s.l

What language is this?

@Timtech javascript's regex

I was tempted (and am still debating internally) to vote to close this as a duplicate of your other regex golf question on the basis that the optimal solutions are within a constant of each other, as witness:
70 chars
^(?!no|c?u|ra|.*(e.[kht]|[^l][gecv]i|[^c]oh?[rn]iu|f.r|ac|sta|bn|has))

I see your point, and in the back of my mind I had thought of this.  What if there was the restriction it needed to be solved without using a global not?

@qw3n, that has two problems. Firstly, as a general rule if you need to prohibit the best option it indicates a weakness in the question. Secondly, it could potentially kill a better solution which casts a fairly wide net and needs to exclude a couple of cases.

When solving the general problem I went from both directions to see what the results would be. This regex was unique from the other and a unique challenge to create, but yes it ignores the fact you can use the shorter regex by adding not. But that was the reason I posted both. I thought it would be a unique challenge from the other one.