Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-4041-

/prog/ challenge

Name: Anonymous 2014-07-02 13:05

A set of integers is sum-free when addition always gets you out of the set (i.e. x + y = z has no solutions -- in other words S + S and S are disjoint). Formally, let S be a subset of N. S is sum-free if for all a,b in S, a+b is not in S.

Now, let S be any set of nonzero integers. Find a subset of size > |S|/3.

You may use your favorite lisp language.

I've got a really nice solution for this one.

Name: Anonymous 2014-07-02 13:11

>>1

integers is sum-free
Truly when programmers are really talented and need a challenge they pick some Haskell as handicap and remove addition for a good measure.

Name: Anonymous 2014-07-02 13:33

>>1
Pick any size you like:

sub sumfree(Int $n) { (1,3,5 ... *)[0..^$n] }

Name: >>3 2014-07-02 13:38

Also works with positive powers >2, etc.

Name: Anonymous 2014-07-02 13:49

Forget it, it's NP-complete.

Name: Anonymous 2014-07-02 13:56

>>3
brilliant

Name: Anonymous 2014-07-02 14:13

>>3,4
You are given the set, not the size! Anyway, lazy lists in perl6 for this? Not bad!

>>5
No it is not.

Name: Anonymous 2014-07-02 14:27

For example, a simple O(n^3) algorithm to check if a subset is sum-free is this:

sumfree s = not . or $ map (flip elem $ s) [i + j | i <- s, j <- s]

Name: Anonymous 2014-07-02 15:30

>>8
Checking every possible solution barely constitutes an algorithm.

Name: Anonymous 2014-07-02 15:37

>>9
Well I hoped someone would at least make an attempt to write this much. My solution is different, if that fuels your muse.

Name: Anonymous 2014-07-02 15:41

>>7
You want a subset of S then? Because your description wasn't clear on that point. I realized what you probably meant after posting.

Anyway, more Perl 6 (whee, junctions)

sub sumfree($l) {
$l.combinations( Int($l/3) ).grep: { (@^a X+ @^a).any == @^a.none }
}

Name: >>11 2014-07-02 15:45

This gives |S|/3, or |S|/3 -1 'cause I'm stupid. The fix is easy, use Int($l/3)+1 combinations.

Name: Anonymous 2014-07-02 15:58

Does it have to be a proper subset? Because otherwise you can just return S.

Name: Anonymous 2014-07-02 15:59

Does it have to be a proper subset? Because otherwise you can just return S.

Name: Anonymous 2014-07-02 16:00

>>13
I think the idea is that the subset is sum-free.

Name: Anonymous 2014-07-02 16:04

>>15
No, it's not. Nowhere in the OP is it said that the subset has to be sum-free. Therefore, "S" is a valid answer. That's probably that clever solution that OP mentioned.

Name: Anonymous 2014-07-02 16:39

>>11,12
combinations is a nice function (or method or prodecure, or whatever the proper terminology is :P). What I understand of this is that you are checking all sets of cardinality |S|/3 + 1 and find a sumfree one. The problem is, even though I can guarantee to you the existence of a sum-free set with more than |S|/3 elements, I'm not saying you can find one for all k > |S|/3. k is to be found as well as the set (the spec in >>1 does not require this, but your function depends on it). So you need to alter your function to continue searching for sum-free subsets starting from |S|/3 + 1 and going up to |S|, until you (surely) hit one.

>>12,13,16
No the spec was wrong, sigh... I hate myself for giving you a wrong spec. I will retype this so that you don't get the wrong idea, excuse the lack of bbcode.

A set of integers is sum-free when addition always gets you out of the set (i.e. x + y = z has no solutions -- in other words S + S and S are disjoint). Formally, let S be a subset of Z. S is sum-free if for all a,b in S, a+b is not in S.
Now, let X be any set of nonzero integers. Find a subset S of X, such that S is sum-free and size(S) > size(X)/3.

In short, your program is given X and produces S.

Anyway I won't post the solution yet as to give you some time and not ruin this for anyone else who wants to try.

Name: Anonymous 2014-07-02 17:10

>>17
Correct me if I'm wrong, but:

forall positive k < |S|, there exists k = |S'| where S' is a subset of S, and S and S' are sum-free.

The reasoning is removing any element from S is sum-free-preserving since it only removes opportunities to find sums on S.

So, if you have an existence proof of positive k>|S|/3, there's one for forall positive k' =< k by way of repeated application of the above.

Name: Anonymous 2014-07-02 17:12

CUM-FREE

Name: Anonymous 2014-07-02 17:35

>>18
You are right! Your wording is a bit hairy -- but in any case your code is fine. :)

Okay so we have the bruteforce method, and in perl6 too. I will post my own method in a while (today or tomorrow), as I intend to write it in haskell and I need to brush up my skills a bit.

Name: Anonymous 2014-07-02 17:54

My code thusfar,
-- Ripping http://www.haskell.org/haskellwiki/Prime_numbers#Postponed_Filters
-- This is a lazy list of prime numbers

primesPT = 2 : primes'
where
primes' = sieve [3,5..] 9 primes'
sieve (x:xs) q ps@ ~(p:t)
| x < q = x : sieve xs q ps
| True = sieve [x | x <- xs, rem x p /= 0] (head t^2) t

-- returns True if an integer is of the form 3k + 2
myCond n = 0 == mod (n - 2) 3

-- return first element in list satisfying predicate
find predicate list = head $ dropWhile (not . predicate) list

-- we need to find a prime of the form 3k + 2 that is larger than 2 max |x_i|

Name: Anonymous 2014-07-02 18:39

>>20
I nearly wrote the nonexistence test in a way that makes it obvious, by doing [&&] ((@^a X+ @^a) X!= @^a). It can't become false by removing elements that are &&-reduced. (Reduction is seeded with the apropriate identity value, +: 0, *: 1, ||: False, &&: True, etc.)

Name: Anonymous 2014-07-02 18:48

If S is sum free every subset of S is sum free. Let L be a subset of S and suppose x,y are in L. Because S is sum free and x,y are in S, we have x + y is not in S. Because L is a subset of S, x + y is not in L. Therefore, L is sum free.

Name: Anonymous 2014-07-02 19:14

This is all basic discrete math. Is anyone here even a third year undergrad?

Name: Anonymous 2014-07-02 19:15

>>20

Your wording is a bit hairy

Just like my anus!

Name: Anonymous 2014-07-02 19:41

>>23
That's better but for some reason I like induction.

Name: Anonymous 2014-07-02 19:59

>>26
Induction wont work if the set is not countable.

Name: >>27 2014-07-02 20:13

Oh S was finite.

Name: Anonymous 2014-07-02 21:48

>>27-28
lol, f'real

but wouldn't the fact that we're dealing with subsets of N rule out uncountable sets?

Name: Anonymous 2014-07-02 22:01

Shalom!

Name: Anonymous 2014-07-02 23:14

sub s {
return @_[0..(@_/3)];
}

Name: L. A. Calculus !jYCj6s4P.g 2014-07-03 0:53

>>1
DER DOESNT EXIST A DECENT CHALLENGE IN UR HED, DOES DER, YA FUCKIN MATH BOY RETOID?

Name: Anonymous 2014-07-03 1:33

>>32
Could you point us to what you consider as decent programming challenges please?

Name: Anonymous 2014-07-03 4:04

>>29
You can restrict yourself to that, but if S is sum free any subset of S will also be sum free. It doesn't matter if S is countable or not. So sum free subsets aren't very interesting. You could consider sum free supersets. Those seem interesting.

Name: Anonymous 2014-07-03 8:08

>>1
What is the complexity of your solution?

Name: L. A. Calculus !jYCj6s4P.g 2014-07-03 8:23

>>33
WRITE A PROGRAM DAT DRAWS A RANDOM DACHSHUND. DA DACHSHUNDS CUD VARY IN SIZE, COAT COLOUR, FUR LENGTH, ETC. IDEALLY, EACH TIME U RUN DA PROGRAM, U'LL GET A UNIQUE DACHSHUND DRAWING.

U CAN IMPLEMENT DIS HOWEVER U WANT: WRITE UR OWN DOMAIN SPECIFIC LANGUAGE, OUTPUT PNG FILES, OUTPUT WAVEFRONT OBJ FILES, RENDER WITH OPENGL/SDL, WATEVER! ADD WATEVER FEATURES U WANT. U CUD OUTPUT 64x64 DESKTOP ICONS 4 ALL I FUKIN CARE, SO LONG AS DEY LOOK LIKE DACHSHUNDS AND DA OUTPUT HAS SOME VARIATION EACH TIME U RUN IT. DA SKY'S DA FUCKIN LIMIT! HELL, U DONT EVEN NEED TO DO DACHSHUNDS. U CAN DO WHATEVER SO LONG AS U STICK WITH DA BASIC CONCEPT.

NOW, ARE U A BUNCH OF UNIMAGINATIVE CODE MONKEYS OR DO U FUKIN MATH BOIZ HAVE A SPARK OF CREATIVITY IN UR SOULS, HUH?

Name: Anonymous 2014-07-03 8:32

>>36
I could just vary the hue of a picture of a dachshund each time you run the program, thus giving a different coat colour and satisfying the requirements.

Name: Anonymous 2014-07-03 8:51

Are these dachshunds turing complete?

Name: L. A. Calculus !jYCj6s4P.g 2014-07-03 9:15

>>37
DA ONLY REQUIREMENT IS DAT UR PROUD OF UR WORK WHEN UR DONE. IF WHAT U DESCRIBED IS ALL U CAN THINK OF RIGHT NOW, GO AHEAD N WRITE IT. ONCE UR DONE WRITING IT, THINK ABOUT HOW U CAN IMPROVE IT. N DON'T BE AFRAID TO START OVER FROM SCRATCH.

>>38
U TELL ME! ARE UR DACHSHUNDS GONNA BE TURING COMPLETE?

Name: Anonymous 2014-07-03 10:10

>>35
First a prime p that does not divide any of the x in Χ needs to be found. Then that prime can be used to generate linearly a sumfree subset. I still haven't implemented the details. It's all in 'the probabilistic method' though.

>>39
Can it be siamese cats instead? They're purring complete

Name: L. A. Calculus !jYCj6s4P.g 2014-07-03 10:14

>>40
DOGS R 4 BOYZ, CATS R 4 GIRLZ

Name: Anonymous 2014-07-03 11:22

>>40
Why are you ``generating'' the subset when you should be selecting elements from the superset?

Name: Anonymous 2014-07-03 11:38

>>42
That's what I meant, that's what the code does. After the prime is found (say, in form 3k + 2), a loop is run, 1<=i<=p. Calculate {i*x_j mod p}. These sets are sum-free, and one is guaranteed to be at least n/3 + 1 in size.

I promise code, one of these days.

Name: Anonymous 2014-07-03 15:23

>>34
The point was to show the solution in >>11-12 was correct for the purposes of the challenge.

Name: Anonymous 2014-07-03 16:52

>>41
Get a load of this fuckin 1950s retard. Go back there you stupid dog fucking virgin nigger.

Name: Anonymous 2014-07-03 16:59

NIGGER

Name: Anonymous 2014-07-04 19:11

>>45
Get a load of this fucking 1950's piece of shit. Go back there you theist shitlord.

Name: Anonymous 2014-07-05 12:13

So are you going to post your solution?

Name: Anonymous 2014-07-05 13:46

>>48
Here's pseudocode:
Input:
Let X = {x_i} be the given set.

Output:
Find a prime p such that:
p = 3k + 2
p > 2max{|x_i|}

For 1 <= j < p:
let S = { j*x_i mod p }
if |S| > |X|/3 break

return S

Sorry I'm not writing any code in a real language but I'm messing with some emacs modes right now. Btw, the book I read this from mentions that the requirements for p can be dropped: It is sufficient that p simply does not divide any of the |x_i|. I did not check if the algorithm works as-is with such a p, and that is what I intented to do when I said I'll post code in a few days, or else I would simply post an implementation of the pseudo-code I just posted.

Sorry for the delay.

Name: Anonymous 2014-07-06 16:34

>>41
AAAWWW LQQK DAAAAAAAA, AN0THER 01D FUK FACE 01D HERPEZ DAMN WH0RE 2 LQQK AT ANN HEAR WAT DA DAMN B1MB0 B0Z0 B1TCH BASTARD HAZZ 2 SAY FR0M HRR 01D MUDD M0UTH H01E, HRR DAMN MAMA ANN DADA MUST B REA1 FUK1N PR0UD 0F DER DUMB ASS CUP1D S0 STUP1D DAMN 2 HE11 DAMN DAUGTHER 4 ACT1N TH1Z WAY 1NN FR0NT 0F M1LL1ONZ 0F PPL DA D0NT EVEN CARE N0R WANT 2 HEAR HRR 01D FAT S0 SAD ASS TALK , N0TT EVEN 4 A FUK1N DAMN M1NUTE, U R A FUK1N F0U1 DAMN F001, S0 U D0NT CARE AS WE REA11Y D0NT CARE 1F U CR0AK 2MORROW U DUMB ASS BEEEEEEEECCHHAAAAAAA :-)
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode + RSS -