Teaser

Behold this formidable drawing:

Can you draw this in a single stroke? Give it a try.

Can you do this one, now:

Give it a try.

How it works

These "make this drawing with one pen stroke" problems are problems with a rather simple solution. For each vertex, compute its degree. If all vertices have an even degree or if only two vertices have an odd degree, this is possible. In any other case, it is impossible. This is the same as finding an Eulerian path in the graph. This is also related to the very famous seven bridges of Königsberg puzzle.

For the first drawing, the degrees are

   2
/   \
4-----4
|\   /|
|  4  |
|/   \|
3-----3


so we are in the second possible case, as all numbers are even except for the two 3s in the bottom. What is more, when we have odd numbers, we have to start in one of them and finish in the other. When everything is even, we can start wherever we want but we will finish where we started.

For the second drawing it is impossible, as there are too many odd degrees:

     2
/   \
5-----5
/|\   /|\
2 |  4  | 2
\|/   \|/
5-----5
\   /
2


Given the degrees of the edges as input, decide if a corresponding drawing could be done in a single pen stroke. Output Truthy if such a feat is possible and output Falsy otherwise.

Input

The degrees of the vertices in any sensible format, such as

• an array of integers like [2,4,4,4,3,3] or [2,5,5,2,4,2,5,5,2]
• separate arguments to a function, like f(2,4,4,4,3,3) or f(2,5,5,2,4,2,5,5,2)

Output

A Truthy value if all numbers are even or exactly two of them are odd, Falsy otherwise.

Test cases

Truthy

[2, 4, 4, 3, 3]
[2, 2]
[1, 2, 3, 4, 6, 8]
[2, 4, 2, 4, 2, 4, 2, 4]
[8, 6, 8, 2, 2, 3, 11]
[1, 3]
[8]


Falsy

[1, 2, 3, 4, 5, 6]
[2, 3]
[9]
[7, 2, 2, 2]
[4, 2, 7]
[3, 3, 3, 3]
[1, 2, 3, 1, 1]
[1, 1, 4, 1, 1]
[7, 7, 7, 7, 7, 7, 7, 7]


This is so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

• Amazingly, none of your falsy test cases can really come from a graph! Feb 15, 2020 at 9:54
• Even then the sum of the degrees should be twice the number of edges and therefore an even number Feb 15, 2020 at 10:09
• Are you saying impossible lists of integers may be inputs? If so I think it should be clear in the spec (i.e. "The degrees of the vertices" would not be a correct description of the input). Feb 15, 2020 at 12:54
• As far as I know, these conditions are necessary but not sufficient i.e. one-strokyness implies them, but not the other way around Feb 16, 2020 at 18:23
• Related puzzle codeforces.com/problemset/problem/788/B
– qwr
Feb 18, 2020 at 0:12

Python, 31 bytes

lambda l:sum(n%2for n in l)|2<3


Try it online!

We use k|2<3 to check that k is either 0 or 2. This works because the bit operation |2 sets the bit for place-value 2, so to get a result that's 2 or less, there must be no other bits set.

• A really good golf, as per usual! +1
– RGS
Feb 15, 2020 at 21:40

Wolfram Language (Mathematica), 25 bytes

(a=Tr@Mod[#,2])==0||a==2&


Try it online!

• +1 on this really short submission! Tr is summing everything, right?
– RGS
Feb 15, 2020 at 21:43
• @RGS If I recall correctly, Tr calculates the trace of a matrix, but for a vector that's simply the sum of the elements.
– Neil
Feb 16, 2020 at 0:09

05AB1E, 5 4 bytes

Thanks to 05AB1E's weird boolification system, any number but 1 is falsy.

-1 Thanks to Jonathan Allan

ÉO1α


Try it online!

Explanation

É     Vectorizing n % 2
O    Sum the resulting list
1α  |n - 1|

• Are you going to submit answers in all the languages you know..? XD
– RGS
Feb 15, 2020 at 9:48
• I believe any integer but 1 is falsey in 05AB1E, if so you don't need the Θ. Feb 15, 2020 at 13:22
• This is incredibly short! Good job
– RGS
Feb 15, 2020 at 21:45

Turing Machine But Way Worse, 1245 bytes

0 0 0 1 1 0 0
0 1 0 1 2 0 0
1 2 1 1 3 0 0
1 3 1 1 4 0 0
0 4 0 1 5 0 0
1 4 1 1 5 0 0
0 5 0 1 6 0 0
1 5 1 1 6 0 0
0 6 0 1 7 0 0
1 6 1 1 7 0 0
0 7 0 1 0 0 0
1 7 1 1 8 0 0
0 8 0 1 9 0 0
0 9 0 1 a 0 0
1 a 1 1 b 0 0
1 b 1 1 c 0 0
0 c 0 1 d 0 0
1 c 1 1 d 0 0
0 d 0 1 e 0 0
1 d 1 1 e 0 0
0 e 0 1 f 0 0
1 e 1 1 f 0 0
0 f 0 1 0 0 0
1 f 1 1 8 0 0
0 b 0 1 k 0 0
0 3 0 1 4 0 0
0 g 0 1 h 0 0
0 h 0 1 i 0 0
1 i 1 1 j 0 0
1 j 1 1 k 0 0
0 k 0 1 l 0 0
1 k 1 1 l 0 0
0 l 0 1 m 0 0
1 l 1 1 m 0 0
0 m 0 1 n 0 0
1 m 1 1 n 0 0
0 n 0 1 g 0 0
1 n 1 1 o 0 0
0 o 0 1 p 0 0
0 p 0 1 q 0 0
1 q 1 1 r 0 0
1 r 1 1 s 0 0
0 s 0 1 t 0 0
1 s 1 1 t 0 0
0 t 0 1 u 0 0
1 t 1 1 u 0 0
0 u 0 1 v 0 0
1 u 1 1 v 0 0
0 v 0 1 g 0 0
1 v 1 1 o 0 0
0 r 0 1 A 0 0
0 j 0 1 k 0 0
0 w 0 1 x 0 0
0 x 0 1 y 0 0
1 y 1 1 z 0 0
1 z 1 1 A 0 0
0 A 0 1 B 0 0
1 A 1 1 B 0 0
0 B 0 1 C 0 0
1 B 1 1 C 0 0
0 C 0 1 D 0 0
1 C 1 1 D 0 0
0 D 0 1 w 0 0
1 D 1 1 E 0 0
0 E 0 1 F 0 0
0 F 0 1 G 0 0
1 G 1 1 H 0 0
1 H 1 1 I 0 0
0 I 0 1 J 0 0
1 I 1 1 J 0 0
0 J 0 1 K 0 0
1 J 1 1 K 0 0
0 K 0 1 L 0 0
1 K 1 1 L 0 0
0 L 0 1 w 0 0
1 L 1 1 E 0 0
0 H 0 1 0 0 1
0 z 0 1 A 0 0
0 2 1 1 M 0 0
0 y 1 1 M 0 0
0 q 1 1 M 0 0
0 M 1 1 N 0 0
0 N 0 1 O 0 0
0 O 0 1 P 0 0
0 P 0 1 Q 0 0
0 Q 1 1 0 1 1
0 a 0 1 0 0 1
0 i 0 1 0 0 1
0 G 0 1 0 0 1


Try it online!

Input: A list like n, n, n, n, ...
Output: (blank) for falsy, 1 for truthy

• I take my hat off to you for your work :p +1
– RGS
Feb 17, 2020 at 13:52
• I didn't realize this existed until today. I'm so honored to have someone use my programming language-- especially when it's for a non-trivial problem-- so this is the first time I've come back from the dead on SE just to upvote this solution. Oct 31, 2020 at 1:46

Charcoal, 8 bytes

⁼¹↔⊖Σ﹪Ａ²


Try it online! Link is to verbose version of code. Port of @ovs' 05AB1E answer. Explanation:

      Ａ     Input array
﹪ ²    Vectorised modulo literal 2
Σ       Sum
⊖        Decremented
↔         Absolute
⁼¹          Equals literal 1


There are other ways to check for 0 or 2 for the same byte count, such as Not(Decremented(Absolute(Decremented(...)))), Equals(2, BitwiseOr(2, ...)), or Count("02", Cast(...)) (careful not to use "20" of course).

• Thanks for your submission! +1
– RGS
Feb 15, 2020 at 21:40

Retina 0.8.2, 18 bytes

M[13579]\b
^[02]$ Try it online! Link includes test cases. Explanation: M[13579]\b  Count the number of odd numbers. ^[02]$


Compare to 0 or 2.

JavaScript (ES6), 29 bytes

a=>a.map(x=>m>>=x&1,m=5)&&m&1


Try it online!

How?

We start with the bitmask $$\m=101_2=5_{10}\$$ and right-shift it by one position for each odd value in the input array. The final result is given by the parity of $$\m\$$.

• Ah this feels really clever! +1
– RGS
Feb 15, 2020 at 21:47

Python 3, 34 bytes

lambda a:sum(n%2for n in a)in(0,2)


Try it online!

• Good job on this one! +1
– RGS
Feb 15, 2020 at 9:47

05AB1E, 6 5 bytes

-1 byte thanks to a'_'.

ÉO<ÄΘ


Try it online!

Explanation

É       is the number odd (vectorizes over the input list)
O      sum (number of odd values)
<     decrement (number of odd values - 1)
Ä    absolute value (|number of odd values - 1|)
Θ   equal to 1 (|number of odd values - 1| == 1)

• 5 bytes by using a == 1 built-in. I guess you win.
– user92069
Feb 15, 2020 at 10:28
• @a'_' thanks a lot. It took me a while to understand this because lowercase and uppercase theta look much too similar.
– ovs
Feb 15, 2020 at 10:39
• @ovs let's ask Greece to change their alphabet a bit! +1 on your short submission
– RGS
Feb 15, 2020 at 21:41

dc<<<grep -c [13579]$d2-*p  Try it online! Input is on stdin: one number per line. Output is on stdout: 0 is truthy, any non-zero value is falsy. How it works: • grep counts the number n of lines ending with an odd digit; • dc then computes and prints n*(n-2), which is 0 iff n equals 0 or 2. Excel, 50 bytes =ISNUMBER(FIND(SUMPRODUCT(--(MOD(A:A,2)=1)),"02"))  MOD(A:A,2)=1 to find odd number SUMPRODUCT() to count them FIND( ,"02") to check if 0 or 2 ISNUMBER() to converts to TRUE/FALSE Feels very clunky, hope to refine... • Looks nice :D +1 – RGS Feb 17, 2020 at 17:42 C++ (gcc), 73 64 bytes I don't know why I keep trying. int f(int*a,int s){int o=1;for(;s;)o+=a[--s]%2;return o%2&&o<4;}  Commented : int f(int*a,int s){ // function definition int o=1; // odd counter starts at 1 because then parity of truthy inputs is one for(;s;) // Use size arg as counter and iterate backwards (Thanks @MitchellSpector) o+=a[--s]%2; // check for odd, add parity return o%2&&o<4; // Valid values for odd are 0 and 2 (or rather 1 and 3) // Solve with parity and range check }  TIO-k6qqj7ln • You keep trying because this is fun! +1 – RGS Feb 16, 2020 at 23:55 • Nice... Keeping the basic idea, here's how you can get it down from 73 to 64 bytes: int f(int*a,int s){int o=1;for(;s;)o+=a[--s]%2;return o%2&&o<4;} Feb 17, 2020 at 1:53 • @MitchellSpector My good coding practice of not editing the arguments is showing!! Feb 17, 2020 at 17:20 • Suggest o&o<4 instead of o%2&&o<4 May 4, 2020 at 7:28 C# (Visual C# Interactive Compiler), 26 bytes p=>(p.Count(n=>n%2>0)|2)<3  Try it online! Thanks to answer of @xnor -1B 27 bytes p=>(p.Count(n=>n%2>0)&-3)<1  Try it online! This one was my first attempt, but I made mistake at first so I'm publishing it now when I fixed it. • Also a port of the python answer, right? +1 – RGS Feb 17, 2020 at 13:53 • At first I made it by myself, but I made mistake when checking if the count is 0 or 2 so it didn't work as i expected so I got inspired by the |2<3 part. But I found the mistake now, so I will add my original thought (one byte longer) Feb 20, 2020 at 7:29 • really nice answers! Thanks for sharing – RGS Feb 20, 2020 at 9:37 • 22 – dana Mar 5, 2021 at 11:58 Julia 1.0, 15 bytes ~v=sum(v.%2)&-3  Try it online! A port of Gymhgy's Japt answer (0 as Truthy, other numbers as Falsy). 17 bytes porting Arnauld's JS solution : ~v=5>>sum(v.%2)%2 Try it online! And an obligatory port of the popular 05AB1E solution, at 19 bytes: ~v=abs(sum(v.%2)-1) Try it online! MATL, 6 bytes osq|1=  Try it online! I herd we're portin 05AB1E solutions! A port of Arnauld's JS solution while we're at it (8 bytes): osW5w/ko Try it online! And one of Gymhgy's Japt answer (6 bytes, 0 as Truthy, other numbers as Falsy): os3_Z& Try it online! (though, os2FZ: is a more straightforward implementation of the idea in MATL Try it online!) Keg, 13 bytes ÷⑷2%⑸⅀:0=$2=+


Try it online!

Simply using everyone else's algorithm!

• Why bother coming up with your own algorithm if everyone else is doing great, right? +1
– RGS
Feb 15, 2020 at 21:48
• @RGS Exactly! Who cares about originality anyway! :P Feb 15, 2020 at 21:49

Japt-!, 7 bytes

èu a1 É


Try it

• Thanks for your submission! +1 were you the one designing the Japt interpreter?
– RGS
Feb 15, 2020 at 21:46
• Yes, @RGS, that interpreter is my creation. Feb 16, 2020 at 0:41
• it looks really good! I just wanted you to know that! Good job on that :)
– RGS
Feb 16, 2020 at 10:56

Wd, 8 7 bytes

♦æ╥└¬y÷


Uncompressed:

2mJ1-z1=


Explanation

2m       % Modulo the list by 2, auto-vectorizes.
J      % Sum the list.
1-    % Decrement by 1.
z   % Absolute value.
1= % Is this 1?

• When you look at this on mobile the first character is the moderator diamond. Feb 16, 2020 at 1:08
• Yes, but without the aeTLlyt. Feb 16, 2020 at 15:19

Stax, 8 bytes

This method is shorter in Stax.

ƒ╟⌡≡ù₧╬)


Run and debug it

Explanation

{2%m       Map modulo 2 over the input
|+     Sum the resulting list
02\  In the list [0, 2]:
# How many times does this number appear?


PHP, 39 43 bytes

for(;$n=$argv[++$i];)$s+=$n%2;echo!($s&-3);


Try it online!

• Thanks misread the question! Fixed. Feb 15, 2020 at 20:43
• @Arnauld thanks for the help here :)
– RGS
Feb 15, 2020 at 21:46

Perl 5-pa, 20 bytes

$_=(2|grep$_%2,@F)<3


Try it online!

Borrows the |2<3 trick from @xnor's Python answer

• Good job porting xnor's trick and getting an answer shorter than his :)
– RGS
Feb 15, 2020 at 21:46

Japt-!, 6 bytes

èu &-3


Try it

èu &-3        Full program taking in array of degrees U
èu            Amount of odd numbers in array
&          Bitwise AND
-3        With -3; -3 has very bit set except of the second bit (1111...11101)
-!            Zero -> True, Other numbers -> False

• Thanks for the Japt submission! Can't you have several test cases in the Japt interpreter?
– RGS
Feb 15, 2020 at 21:44
• I understand, thanks for the explanation!!
– RGS
Feb 15, 2020 at 21:51

GolfScript, 11 bytes

{2%+}*(2?(!


Try it online!

My first go at it, may shrink it a bit. I made it so 1 is true, 0 is false, but if you're okay with the other way around, I can do different things :)

Short explanation; Convert all the elements to mod 2 and sum them. The only valid answers would be 0 or 2. Now, subtract 1 and square them. 0 is -1 is 1. 2 is 1 is 1. 0 and 2 both give you 1. Lastly, subtract 1 and perform a not operation to make all non-0, non-2 values to a 0 and the 0-2s to a 1.

Kind of roundabout, and I'm sure I can cut two characters somewhere.

• This looks nice! +1 thanks for your submission
– RGS
Feb 16, 2020 at 23:55

APL (Dyalog Unicode), 10 bytesSBCS

0 2∊⍨1⊥2∘|


Try it online!

Because a challenge needs an APL answer.

How it works

0 2∊⍨1⊥2∘|
2∘|  ⍝ Modulo 2
1⊥     ⍝ Sum
0 2∊⍨       ⍝ Is member of [0 2]?

• Yes it does! +1 for that :)
– RGS
Feb 17, 2020 at 8:03

Whitespace, 102 bytes

[S S S N
_Push_0][S N
S _Dupe_0][N
S S N
_Create_Label_LOOP][S N
S _Dupe][S N
S _Dupe][T  N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve][S N
S _Dupe_input][N
T   T   S N
_If_neg_Jump_to_Label_DONE][S S S T S N
_Push_2][T  S T T   _Modulo][T  S S S _Add][N
S N
N
_Jump_to_Label_LOOP][N
S S S N
_Create_Label_DONE][S N
N
S _Dupe][N
T   S T N
_If_0_Jump_to_Label_TRUTHY][S S S T S N
_Push_2][T  S S T   _Subtract][N
T   S T N
_If_0_Jump_to_Label_TRUTHY][T   N
S T _Print_as_integer][N
N
N
_Exit_program][N
S S T   N
_Create_Label_TRUTHY][S S S T   N
_Push_1][T  N
S T _Print_as_integer]


Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Since Whitespace inputs one integer at a time, the input should contain a trailing -1 so it knows when to stop reading integers and the input is done.
Outputs 1/0 for truthy/falsey respectively.

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer n = 0
Start LOOP:
Integer i = STDIN as input
If(i < 0):
n = n + (i modulo-2)
Go to next iteration of LOOP

Label DONE:
Print 0 as integer to STDOUT
Exit program

Label TRUTHY:
Print 1 as integer to STDOUT

• I was starting to fear this would never happen :( +1 for making me happy on a Monday morning! Quick question: when reading from stdin, is there a default way of knowing the input is over?
– RGS
Feb 17, 2020 at 8:17
• @RGS Whitespace only has two ways to read STDIN input: read as integer and read as character. So no, there isn't a default way of knowing the input is over, unless trying to read a next character that isn't there anymore, after which the program stops with an error. I usually use a newline as indicator when a string input is being asked; -1 if only positive integers are being asked; etc. Feb 17, 2020 at 8:21
• thanks! I was asking because the other day I read your "make a whitespace interpreter" challenge and as I read through the specs, I couldn't figure out how we'd know the input is over when programming in whitespace. For some reason I just kept thinking that, much like brainfck "reads" a 0 when input is over, whitespace must have a similar mechanism :p but it really doesn't need to and it doesn't have :)
– RGS
Feb 17, 2020 at 8:33

MathGolf, 6 bytes

¥Σ(±1=


Try it online.

Explanation:

¥       # Take modulo-2 on each integer of the (implicit) input-list
Σ      # Sum those
(     # Decrease it by 1
±    # Take the absolute value
1=  # And check whether this is equal to 1
# (after which the entire stack joined together is output implicitly)

• Cool subtracting by one and then absolute value to check for 0 and 2
– RGS
Feb 17, 2020 at 8:33

Java 8, 28 bytes

s->(s.map(i->i%2).sum()|2)<3


Try it online.

Explanation:

s->               // Method with IntStream parameter and boolean return-type
(s.map(i->i%2)  //  Take modulo-2 for each value in the IntStream
.sum()        //  And them sum those
|2)           //  Take a bitwise-OR with 2
<3         //  And check whether that is smaller than 3

• Keep up the good work +1
– RGS
Feb 17, 2020 at 10:52

Chevron, 172 147 bytes

^__>^n
>^n>^t
^t~s>>^s
0>>^o
0>>^i
^i+1>>^i
^t,^i~c>>^c
->+2??^c~^_i
->-3
^n^c>^n
^n~o>>^z
^o+^z>>^o
^__>^n
->+2?^i=^s
->-9
^o-2>>^p
^o*^p>>^o
>^o


Takes numbers from stdin in the form 2 4 4 3 3.

Outputs 0 or -0 for truthy, anything else falsy.

– RGS
Feb 17, 2020 at 17:47
• Chevron isn't on tio yet, I'll work on that :) Feb 17, 2020 at 17:48
• @RGS it's not tio, but here's something to test on :) ch.superloach.xyz Feb 17, 2020 at 19:39

Vyxal, 6 bytes

∺∑⨪Ȧ1=


Try it Online!

Just another port of the 05ab1e answer.

R, 30 29 bytes

Or **R>=4.1, 22 bytes by replacing the word function with a \.

Edit: -1 byte thanks to @Giuseppe.

function(v)sum(v%%2/2)%in%0:1


Try it online!

Almost straightforward approach.

Less straightforward, but used by many other answers, approach results in the same byte-count:

function(v)(sum(v%%2)-1)^2==1


Try it online!

• 29 bytes? Mar 6 at 19:49
• @Giuseppe nice one, thanks! Mar 6 at 20:08