3
\$\begingroup\$

The idea for this code golf puzzle is from link: The Bridge and Torch Problem

The inspiration for this code golf puzzle is the Bridge and Torch problem, in which d people at the start of a bridge must all cross it in the least amount of time.

The catch is that at most two people can cross at once, otherwise the bridge will crush under their weight, and the group only has access to one torch, which must be carried to cross the bridge.

Each person in the whole puzzle has a specified time that they take to walk across the bridge. If two people cross together, the pair goes as slow as the slowest person.

For this challenge d=4 and for the input you will get a time t and a list of tuple like:

input = (19,[('A', 1), ('B', 3), ('C', 4), ('D', 5)])

Now the task is to find all possible solution how they can cross the bridge within the time t. Solve the problem in the fewest bytes of code possible.

For example for this input:

input =(19,[('A', 1), ('B', 2), ('C', 5), ('D', 10)])

Your solution should look like:

Solution

['Couple A and B cross the bridge']

[' A goes back']

['Couple D and C cross the bridge']

[' B goes back']

['Couple A and B cross the bridge']

Solution

['Couple A and B cross the bridge']

[' A goes back']

['Couple D and A cross the bridge']

[' A goes back']

['Couple C and A cross the bridge']

Solution

['Couple A and B cross the bridge']

[' A goes back']

['Couple C and A cross the bridge']

[' A goes back']

['Couple D and A cross the bridge']

Solution

['Couple A and C cross the bridge']

[' A goes back']

['Couple D and A cross the bridge']

[' A goes back']

['Couple A and B cross the bridge']

Solution

['Couple A and C cross the bridge']

[' A goes back']

['Couple A and B cross the bridge']

[' A goes back']

['Couple D and A cross the bridge']

Solution

['Couple A and D cross the bridge']

[' A goes back']

['Couple C and A cross the bridge']

[' A goes back']

['Couple A and B cross the bridge']

Solution

['Couple A and D cross the bridge']

[' A goes back']

['Couple A and B cross the bridge']

[' A goes back']

['Couple C and A cross the bridge']

The output don't need to be in a specific format.

|improve this question
\$\endgroup\$
  • 5
    \$\begingroup\$ Welcome to the site. It would be nice if you could be a little clearer on the output format. Giving an example of valid output is nice but it only goes so far. It would be nice if people did not have to guess as to what is expected. \$\endgroup\$ – Post Rock Garf Hunter Jul 16 '19 at 18:57
  • \$\begingroup\$ In particular, a list of solutions, where each solution is a list of steps, where each step is a list of people who cross at once, should be allowed because we know every other step is returning. \$\endgroup\$ – lirtosiast Jul 16 '19 at 23:24
  • \$\begingroup\$ This is a borderline dupe of the linked question. The only reason it might not be a dupe is that some languages might not find it as easy to work with lists of paths as with integers. \$\endgroup\$ – Peter Taylor Jul 17 '19 at 6:34

Your Answer

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

Browse other questions tagged or ask your own question.