7
\$\begingroup\$

Note: When I refer to a bridge, I mean it in the non-mathematical sense

Introduction

You are on a network of islands which are connected by wooden bridges and you want to see if you can burn every bridge in the island network. However, you can only burn a bridge once you've walked over it.

Once a bridge has been burned, it has gone and you cannot go back over it. None of the islands are connected.

Since you are going on a stroll, you cannot swim.

Challenge

Given a list of the bridges and which islands they connect, output a truthy value if you can burn every bridge and falsey value if you cannot.

Input

The input will be a list of numbers. A bridge is defined as:

X,Y

Where are X and Y are integers. Each bridge has an integer number which X and Y refer to.

For example,

2,6

Means that there is a bridge between the islands 2 and 6.

The input will be a list of these bridges:

2,6 8,1 8,2 6,1

You may take this a flat array, if you wish.

Rules

The numbers for the islands will always be positive integers, n, where 0 < n < 10. The island numbers will not always be contiguous.

When you walk over a bridge, you must burn it.

You will be given a maximum of eight islands. There is no limit on the number of bridges.

Island networks will always connect together. There will always be exactly one connected component.

This is an undirected network. For example, you can go either way across the bridge 1,2.

Examples

Input > Output
1,2 1,3 1,3 1,4 1,4 2,3 2,4 > Falsey
1,5 1,6 2,3 2,6 3,5 5,6 > Truthy
1,2 1,3 1,4 2,3 2,4 3,4 > Falsey
1,2 > Truthy

Winning

Shortest code in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Can we assume that there will not be more than one bridge between two islands (sorry, didn't notice this during review)? \$\endgroup\$ – HyperNeutrino Jun 26 '17 at 14:31
  • \$\begingroup\$ this is an undirected graph, yes? So I can walk on a (1,2) bridge from 2 to 1 \$\endgroup\$ – vroomfondel Jun 26 '17 at 14:33
  • \$\begingroup\$ @HyperNeutrino No, see the first example where there are two bridges between 1 and 2 and two bridges between 1 and 3 \$\endgroup\$ – Beta Decay Jun 26 '17 at 14:36
  • 1
    \$\begingroup\$ So you're just asking us to check if the graph has an Eulerian path? \$\endgroup\$ – Not a tree Jun 26 '17 at 14:42
  • 1
    \$\begingroup\$ Should "at least one connected component" say "exactly one connected component"? \$\endgroup\$ – Peter Taylor Jun 26 '17 at 16:30
6
\$\begingroup\$

Mathematica, 27 26 bytes

Assuming that it is a connected graph.

Tr@Mod[Last/@Tally@#,2]<3&

Takes a flat list as input.

Example:

In[1]:= Tr@Mod[Last/@Tally@#,2]<3&[{1, 2, 1, 3, 1, 3, 1, 4, 1, 4, 2, 3, 2, 4}]

Out[1]= False
\$\endgroup\$
  • \$\begingroup\$ I'm surprised that there's no builtin for this! \$\endgroup\$ – vroomfondel Jun 26 '17 at 14:55
  • \$\begingroup\$ ...aand there's the built-in :D \$\endgroup\$ – Beta Decay Jun 26 '17 at 15:02
  • \$\begingroup\$ Is the FindEulerianCycle part of that answer useful? \$\endgroup\$ – nmjcman101 Jun 26 '17 at 19:29
6
\$\begingroup\$

Python 2, 102 92 43 bytes (40 in Python 3)

Thanks to @Neil for reminding me that you can't have an odd number of vertices with odd degree – and saving 5 bytes.

lambda x:sum(x.count(a)%2for a in set(x))<3

Try it online!

You can cut it down to 40 bytes in Python 3 (thanks to @shooqie):

lambda x:sum(x.count(a)%2for a in{*x})<3

A graph has a Eulerian trail iff the number of vertices with odd degree is 0 or 2.

This takes the input as a flat list, as explicitly allowed by the spec.

This assumes all of the islands are connected.

\$\endgroup\$
  • \$\begingroup\$ Yup, BetaDecay says you must burn a bridge after walking over it, so I'll delete my comments. \$\endgroup\$ – HyperNeutrino Jun 26 '17 at 14:52
  • \$\begingroup\$ @Rod Oh yeah, true. :P \$\endgroup\$ – HyperNeutrino Jun 26 '17 at 14:52
  • \$\begingroup\$ lambda x:sum(x.count(a)%2for a in{*x})in[0,2] - you need Python 3 though \$\endgroup\$ – shooqie Jun 26 '17 at 15:43
  • \$\begingroup\$ Wow, how does that work? \$\endgroup\$ – Beta Decay Jun 26 '17 at 15:51
  • \$\begingroup\$ @BetaDecay *x "explodes" x into x1,x2,x3..., so you can pass it straight into {} which is essentially syntactic sugar for the set constructor. \$\endgroup\$ – vroomfondel Jun 26 '17 at 15:53
2
\$\begingroup\$

Jelly, 9 bytes

Qċ@€%2S<3

Try it online!

Port of rogaos's Python answer. If you upvote this answer, please upvote that one too. :)

\$\endgroup\$
1
\$\begingroup\$

Pyth, 14 11 10 bytes

>3sm%/Qd2{

Try it online!

My first Pyth program! I'm sure it could be golfed a great deal.

Thanks to @Rod for saving 1 byte by using Q implicitly.

Same general idea as my Python answer.

\$\endgroup\$
  • 1
    \$\begingroup\$ I guess you could reverse the check, to use the last Q implicitly -> >3sm%/Qd2{ \$\endgroup\$ – Rod Jun 26 '17 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.