Un conjunto es libre de sumas si no hay dos elementos (no necesariamente distintos) cuando se agregan juntos son parte del conjunto en sí.
Por ejemplo, no {1, 5, 7}
tiene suma, porque todos los miembros son impares, y dos números impares cuando se suman son siempre pares. Por otro lado, {2, 4, 9, 13}
no es libre de sumas, ya sea 2 + 2 = 4
o se 4 + 9 = 13
suman a un miembro del conjunto.
Escriba un programa o función que tome un conjunto como entrada y genere un valor de Verdad si el conjunto no tiene suma y Falsy de lo contrario.
Ejemplos:
Sum-free:
{}
{4}
{1, 5, 7}
{16, 1, 4, 9}
Not sum-free:
{0}
{1, 4, 5, 7}
{3, 0}
{16, 1, 4, 8}
Respuestas:
Pyth -
85 bytesThanks to @FryAmTheEggman for saving me 3 bytes.
Test Suite.
fuente
2 + 2 = 4
from OP. My answer before FryAmTheEggman's golf actually used.C
ombinations with replacement because of this.Python 2, 41 bytes
s
should be a Python set.Fun fact:
sum-free
is an anagram of my name.fuente
lambda s:not{a+b for a in s for b in s}&s
is the same length. I can't find a way to shorten the negation, sadly.Jelly, 5 bytes
Try it online!
How it works
fuente
JavaScript,
864241 bytesThanks Cᴏɴᴏʀ O'Bʀɪᴇɴ for saving me a ton of bytes off parentheses/curly brackets. Also thanks Neil for pointing out that the function was returning the opposite boolean value than it should have.
I tried to cut down on bytes by redefining
n.some
but that doesn't work because it's a prototype function unfortunately. There might be a better solution withArray.prototype.map
in JS but the some function is really fun.I'm now wondering if there's a shorter way than
.includes
using something such as .indexOf and adding 1 (which would give it a truthy value if it contains the number).Testing:
fuente
n=>n.some(m=>n.some(o=>n.some(p=>m+o==p)))
n.contains(o+p)
which saves you 2 bytes over the innermostsome
.includes
(it was originally going to be calledcontains
but some library has a conflicting definition).MATL, 5 bytes
This outputs an array which is truthy if all entries are
1
and falsey otherwise. Here is a demo to show various truthy/falsey values in MATL.Try it Online
Explanation
fuente
Mathematica, 23 Bytes
fuente
∩
with⋂
(U-22C2). The code right now isn't copypastable into Mathematica.Haskell,
32, 30 bytesSimple solution:
Two bytes saved by @Lynn
fuente
f x=and[a+b/=c|a<-x,b<-x,c<-x]
for 30 bytes.Julia, 18 bytes
Try it online!
fuente
J,
18108 bytes8 bytes saved thanks to miles, and 2 thanks to FrownyFrog!
Matches the original list with the set difference of tabulated sums. This is equivalent to:
for input
y
. This translates to:+/~
returns a table of sums usingy
. Fory =: 16 1 4 9
, this gives:Then, we use
-.
, which produces a list consisting of all elements iny
not in this table. If the list is sum-free, this will produce the same list. Then,-:
checks for equality of lists, which produces the desired output.Old, 18 bytes
+/~
creates a table of the values of the set added to itself, ande.
checks if those members are in the original set. The rest of that is negating the maximal element.fuente
-:]-.&,+/~
for 10 bytes using set difference-.
and list matching-:
-.
already works with cells of y.Retina,
4544 bytesInput is a decimal list of comma-separated numbers. Output is
0
(falsy) or1
(truthy).Try it online! (The first line enables a linefeed-separated test suite.)
Explanation
Stage 1: Substitution
This converts all elements of the input to unary and wraps them in
<...>
. The purpose of the angle brackets is to distinguish a list containing only0
from an empty list (since the unary representation of0
is empty itself).Stage 2: Substitution
We repeat the string 3 times by append it twice at the end.
Stage 3: Match
We now try to find three numbers in the result such that the first two add up to the third. Those matches are counted (this doesn't actually count all such tuples, because matches cannot overlap, but if such a tuple exists it will be found). Hence, we get
0
for sum-free sets and something positive otherwise.Stage 4: Match
Since the previous stage gave the opposite of what we want, we negate the result by counting the matches of
^0
which is1
for input0
and0
for everything else.fuente
Octave,
292125 bytesThanks to Suever! It returns an array. I added
0
at the end to make[]
become sum-free. To verify truthy and falsey in Octave, you can do this:An alternative that returns 0 or 1 is:
fuente
@(s)~ismember(s+s',s)
since arrays can be truthy/falseyClojure,
4737 bytesquite plain solution. uses list comprehension to find all elements which sum is equal to another element.
38 bytes variant:
fuente
#(=(for[a % b % :when(%(+ a b))]a)[])
which can save 10 bytesPerl 6,
24 21 2019 bytesInput is any Positional value like a List.
( a Set is an Associative so you would have to call
.keys
on it. )Test:
fuente
Mathematica
63 6242 bytesThis shorter version benefitted from A Simmons' submission. No element needs to be removed from the list before
IntegerPartitions
is applied.If an element cannot be partitioned into two integers (each from the list), then
IntegerPartitions[#,{2},#]=={}
holds.And
checks whether this holds for every element in the list. If so, the list is sum-free.Examples
False
True
There is a 2, but no odd numbers that differ by 2.
True
fuente
a
defined somewhere else in your workbook? These expressions don't give the desired output when I evaluate them.a
should have been a#
. I corrected it and removed a superfluous@
.Ruby, 36 bytes
Constructs a cartesian product of the set against itself and finds the sum of all elements, then checks for intersection with the original set. Input is arrays, but in Ruby they have enough set operations to make it work out nicely anyways.
-1 byte over my original solution (used
&
instead of-
and compared with[]
) because of inspiration from @feersumTry it here!
fuente
Python, 40 bytes
^
= symmetric difference, new set with elements in either sets but not both>
True if the left set is a superset of the right set.fuente
A is sum-free if the equation a + b = c has no solution with a, b, c ∈ A
. With this definition, the empty set is not sum free, and my answer is correct. But I may be biased.Brachylog, 13 bytes
Explanation
fuente
[2:2]
a subset of 2 elements of[2:4:9]
?[2:4:9]
.R,
3936 bytesCall as
w(s)
, wheres
is the set (actually vector) of values. Here is the output for some test cases:Where
c()
is the concatenation function that takes a bunch of values and makes it a vector.EDIT: Making it an anonymous function to save 3 bytes, thanks to @MickyT.
fuente
function(s)!any(outer(s,s,'+')%in%s)
Racket, 58 bytes
Explanation:
fuente
05AB1E,
95 bytesSaved 4 bytes thanks to Magic Octopus Urn
Try it online!
Explanation
fuente
APL, 8 bytes
Explanation:
Test:
fuente
Haskell, 30 bytes
I think there exists a shorter solution that's more interesting, but I haven't found it.
These are 33 and 34 bytes:
fuente
s
and getting rid of the last part of the comprehsion work?f s=and[notElem(x+y)s|x<-s,y<-s]
, that's 32. There's alsof s=all(`notElem`s)$(+)<$>s<*>s
for 31.Actually, 7 bytes
Try it online!
fuente
♂
)TSQL, 47 bytes
Note: This will only run once, then the table needs to be deleted or dropped to run again. The fiddle editor doesn't allow creation of tables. Therefore the fiddle included in my answer uses 2 extra bytes to compensate for this - the fiddle version doesn't require cleanup.
Fiddle
fuente
Perl, 46 bytes
45 bytes code + 1 byte command line (-p)
Uses a single regex match with Perl's support for 'code expressions' inside the regex to allow for evaluation within a match.
To get around the requirement that the input is unsorted, we repeat the input string three times. This guarantees that the result is after the two operands, and allows the same digit to be matched again (e.g. in the case of input
2 4
).Usage example:
fuente
Factor, 47 bytes
∩ { } =
is equivalent to but shorter thanintersects?
.Σ
is shorter than but equivalent tosum
.Thanks, math.unicode!
testing code:
I'm only confident the first two are correct. It's unclear from the question what the rest should be, so I think it's fine for now.
fuente
PHP, 73 bytes
+8 to turn the snippet into a program, -8 on obsolete variables thanks to insertusernamehere
prints
1
fortrue
, empty output forfalse
usage:
php <filename> <value1> <value2> ...
qualified function for testing (
9486): returns1
or nothingtests
fuente
$i
and$j
you can discard$i=>
as well as$j=>
and save 8 bytes. Unfortunately code snippets are not valid answers. Make it a function or a full program and include that in your byte count and you're ready to go. :)Java, 67 bytes
Input is a
Set<Integer>
. Tests:Output:
fuente
Clojure, 34 bytes
I wrote this before noticing the earlier Clojure solution. Anyway, this one is more compact as it uses the input set as a
pred
function fornot-any?
.fuente
Prolog (SWI),
665649 bytesTry it online!
fuente