14
\$\begingroup\$

While similar to the other water-carrying puzzle, the unique aspects of this challenge make it entirely different.

Beth

Beth is located at an oasis in the middle of a desert. There is plenty of water in the lake, but unfortunately there are only X buckets, each of which has a capacity of Y liters of water.

Beth can carry 2 buckets in her hands, but to survive, she must drink exactly 1 liter after each kilometer she travels. She can also leave some buckets half-way (water does not evaporate).

The challenge

Figure out the formula and write the shortest solution that will work for positive integer values of X and Y and calculate the maximum distance Beth can travel from the oasis. Moving water between the buckets is permitted.

Example

X=3, Y=5

  1. Beth walks 3km with two full buckets. Leaves 1 full bucket behind. The other bucket now has 2L left, which is enough to get home (Beth can have the last drink from the oasis).
  2. She leaves with another two full buckets, arriving with 1 full, plus 2 litres in the other (12L total: 5 + 5 + 2).
  3. Beth can advance to 6KM point and leave bucket with 4L of water in it.
  4. She returns to the 3KM point. She now has exactly 2L to get back to the oasis.
  5. Fill up buckets and travel to 6KM point. She now has 8L of water.
  6. Continue all the way to 15KM point.

Answer is: 15

Input / Output

You can define X/Y directly in the code or read from input. Result could be placed in variable or output, whichever is shortest.

\$\endgroup\$
13
  • 2
    \$\begingroup\$ Is this supposed to be code golf? It's tagged as a code challenge. \$\endgroup\$
    – Dennis
    Jan 6, 2017 at 1:44
  • \$\begingroup\$ Yes, it's code-golf, I added the tag. Come up with a correct formula and express it through the code. \$\endgroup\$
    – romaninsh
    Jan 6, 2017 at 1:46
  • 2
    \$\begingroup\$ I think it's worth expanding on step 1. It wasn't clear to me at first how Beth could travel 6km with only 5 liters of water: she drinks only after each km she travels, and at the last one she's at the oasis. \$\endgroup\$
    – xnor
    Jan 6, 2017 at 7:14
  • 1
    \$\begingroup\$ Could you give a test-case, in the way that a program would output it? \$\endgroup\$
    – Pavel
    Jan 6, 2017 at 8:17
  • 1
    \$\begingroup\$ If Beth leaves a 5L bucket at the 5.5Km point she would have 9.5L of water on her return allowing her to reach 16Km. \$\endgroup\$
    – Neil
    Jan 7, 2017 at 12:17

3 Answers 3

8
\$\begingroup\$

JavaScript (ES6), 25 bytes

x=>y=>((x<3?x:3)+x)*y/2+1
x=>y=>(x<3?x+x:x+3)*y/2+1
x=>y=>(x<3?x:(x+3)/2)*y+1
x=>y=>(x<3?x:x/2+1.5)*y+1

All of these compute the same value; I can't seem to come up with a shorter formulation.

When x is less than 3, you take as much water as you can and walk as far as you can, which is simply x*y+1.

When x is at least 3, you have to start building caches.

From the oasis, you can leave a full bucket at a distance y/2 and return to the oasis. You need 2 buckets to do this, but this is not useful if you only have 2 buckets because you want to be able to fill up 2 buckets when you return to the oasis.

From the oasis, with a bucket at a distance y/2, you can leave a full bucket at a distance y and return to the oasis. You need 3 buckets to do this.

From the oasis, with full buckets at both y and y/2, you can leave a full bucket at a distance 3y/2 and return to the oasis. You need 4 buckets to do this. You then have to leave a full bucket at a distance of y/2 and return to the oasis.

Eventually you can end up with a full bucket at (x-1)y/2. (You cannot leave a full bucket at xy/2 because you would not be able to get back to the oasis, as the round trip is xy, the total capacity of the buckets.)

Using your remaining buckets, you can leave full buckets at (x-3)y/2 ... y or y/2. At this point you simply walk as far as you can, picking up your full buckets as you go. When you reach (x-1)y/2 you still have two full buckets left, allowing you to reach (x+3)y/2.

The extra 1 comes from the quirk in the rules allowing you to walk your last mile without having any water. Although the example shows that you can leave the buckets slightly further away than described above, this actually does not help you walk any further, as you either have to leave less water or drink the water from the bucket as you reach it before you can move on.

\$\endgroup\$
1
  • \$\begingroup\$ This is a really nice writeup. \$\endgroup\$ May 4, 2020 at 2:23
3
+200
\$\begingroup\$

APL (Dyalog Unicode), 12 bytesSBCS

1+2÷⍨⊢×⊣+3⌈⊣

Dyadic train taking X on the left and Y on the right.

Try it online! This uses @Neil's first formulation, so be sure to upvote that one as well.

how it works:

          3⌈⊣ ⍝ Find the maximum between the left (⊣) argument (X) and 3
        ⊣+    ⍝ and sum that to the left (⊣) argument (X),
     ⊢×       ⍝ which we then multiply by the right (⊢) argument (Y)
  2÷⍨         ⍝ and divide by 2.
1+            ⍝ Finish of by adding 1.
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

D3‚à+*;>

Port of @Neil's formula, so make sure to upvote him!!

$$d_{X,Y}=\begin{cases} \dfrac{(3+X)\times Y}{2}+1 &\text{ if }X<3\\ \\ \dfrac{2X\times Y}{2}+1 &\text{ if }X\geq3 \end{cases} $$

Try it online.

Explanation:

D         # Duplicate the first (implicit) input-integer X
 3‚       # Pair it with 3: [X,3]
   à      # Pop and push its maximum
    +     # Add it to the duplicated X (3+X if X<3; X+X if X>=3)
     *    # Multiply it by the second (implicit) input-integer Y
      ;   # Halve that
       >  # And increase it by 1
          # (after which the result is output implicitly)
\$\endgroup\$
3
  • \$\begingroup\$ If your posting this 8 byte solution means my (to be awarded) APL bounty is going to be cut in half... Then I'll cry slightly :) \$\endgroup\$
    – RGS
    May 3, 2020 at 14:40
  • \$\begingroup\$ @RGS I don't think it should be halved, since it states "The answer wins the challenge when posted." in Adám's rules. :) \$\endgroup\$ May 3, 2020 at 15:15
  • \$\begingroup\$ Lucky me :) Have a +1 \$\endgroup\$
    – RGS
    May 3, 2020 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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