Hourglass puzzle

Hourglass puzzle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

Given two hourglass of 4 minutes and 7 minutes, the task is to measure 9 minutes.

Notes

Implemented as a 1-player game.

Go

Translation of: Julia

<lang go>package main

import (

   "fmt"
   "log"

)

func minimum(a []int) int {

   min := a[0]
   for i := 1; i < len(a); i++ {
       if a[i] < min {
           min = a[i]
       }
   }
   return min

}

func sum(a []int) int {

   s := 0
   for _, i := range a {
       s = s + i
   }
   return s

}

func hourglassFlipper(hourglasses []int, target int) (int, []int) {

   flippers := make([]int, len(hourglasses))
   copy(flippers, hourglasses)
   var series []int
   for iter := 0; iter < 10000; iter++ {
       n := minimum(flippers)
       series = append(series, n)
       for i := 0; i < len(flippers); i++ {
           flippers[i] -= n
       }
       for i, flipper := range flippers {
           if flipper == 0 {
               flippers[i] = hourglasses[i]
           }
       }
       for start := len(series) - 1; start >= 0; start-- {
           if sum(series[start:]) == target {
               return start, series
           }
       }
   }
   log.Fatal("Unable to find an answer within 10,000 iterations.")
   return 0, nil

}

func main() {

   fmt.Print("Flip an hourglass every time it runs out of grains, ")
   fmt.Println("and note the interval in time.")
   hgs := [][]int{{4, 7}, {5, 7, 31}}
   ts := []int{9, 36}
   for i := 0; i < len(hgs); i++ {
       start, series := hourglassFlipper(hgs[i], ts[i])
       end := len(series) - 1
       fmt.Println("\nSeries:", series)
       fmt.Printf("Use hourglasses from indices %d to %d (inclusive) to sum ", start, end)
       fmt.Println(ts[i], "using", hgs[i])
   }

}</lang>

Output:

Flip an hourglass every time it runs out of grains, and note the interval in time.

Series: [4 3 1 4 2 2]
Use hourglasses from indices 2 to 5 (inclusive) to sum 9 using [4 7]

Series: [5 2 3 4 1 5 1 4 3 2 1 4 5 2 3 4 1]
Use hourglasses from indices 4 to 16 (inclusive) to sum 36 using [5 7 31]

Julia

Implemented as a game solver rather than as a game with user input. <lang julia>function euclidean_hourglassflipper(hourglasses, target::Integer)

   gcd(hourglasses) in hourglasses && !(1 in hourglasses) && throw("Hourglasses fail sanity test (not relatively prime enough)")
   flippers, series = deepcopy(hourglasses), Int[]
   for i in 1:typemax(target)
       n = minimum(flippers)
       push!(series, n)
       flippers .-= n
       for (i, n) in enumerate(flippers)
           if n == 0
               flippers[i] = hourglasses[i]
           end
       end
       for startpoint in length(series):-1:1
           if sum(series[startpoint:end]) == target
               println("Series: $series")
               return startpoint, length(series)
           end
       end
   end

end

println("Flip an hourglass every time it runs out of grains, and note the interval in time.") i, j = euclidean_hourglassflipper([4, 7], 9) println("Use hourglasses from step $i to step $j (inclusive) to sum 9 using [4, 7]") i, j = euclidean_hourglassflipper([5, 7, 31], 36) println("Use hourglasses from step $i to step $j (inclusive) to sum 36 using [5, 7, 31]")

</lang>

Output:

Flip an hourglass every time it runs out of grains, and note the interval in time.
Series: [4, 3, 1, 4, 2, 2]
Use hourglasses from step 3 to step 6 (inclusive) to sum 9 using [4, 7]
Series: [5, 2, 3, 4, 1, 5, 1, 4, 3, 2, 1, 4, 5, 2, 3, 4, 1]
Use hourglasses from step 5 to step 17 (inclusive) to sum 36 using [5, 7, 31]

Phix

<lang Phix>procedure print_solution(sequence eggtimers, tries, integer target, pdx)

   sequence soln = {tries[$]}, remain
   integer n = length(eggtimers), tdx = tries[$][3], t, flipbits
   string et = ""
   for timer=1 to n do
       if timer=n then et &= " and "
       elsif timer>1 then et &= ", " end if
       et &= sprintf("%d",eggtimers[timer])
   end for
   printf(1,"\nSolution for %d minutes with %s minute eggtimers:\n",{target,et})
   while tdx do
       if tdx=pdx then soln &= 0 end if
       soln = append(soln,tries[tdx])
       tdx = tries[tdx][3]
   end while
   soln = reverse(soln[1..$-1])
   integer tp = 0, ro = 0
   sequence premain = repeat(0,n)
   for i=1 to length(soln) do
       if soln[i]=0 then
           puts(1,"start timer\n")
       else
           {remain,t,?,flipbits} = soln[i]
           sequence flip = int_to_bits(flipbits,n)
           string fs = "", lv = ""
           for timer=1 to n do
               if flip[timer] then
                   if length(fs) then fs &= " and " end if
                   fs &= sprintf("%d",eggtimers[timer])
                   if premain[timer] then
                       fs &= sprintf(" (leaving %d)",eggtimers[timer]-premain[timer])
                   end if
               end if
               if remain[timer]=0 then
                   if flip[timer] or premain[timer]!=0 then
                       ro = eggtimers[timer]
                   end if
               else
                   if length(lv) then lv &= " and " end if
                   lv &= sprintf("%d in %d",{remain[timer],eggtimers[timer]})
               end if
           end for
           lv = iff(length(lv)?" (leaving "&lv&")":"")
           printf(1,"At t=%d, flip %s, then when %d runs out%s...\n",{tp,fs,ro,lv})
           tp = t
           premain = remain
       end if
   end for
   printf(1,"At t=%d, stop timer\n",{tp})

end procedure

procedure solve(sequence eggtimers, integer target)

   integer n = length(eggtimers), tdx = 1, t, pdx
   sequence remain = repeat(0,n),
            tries = Template:Remain,0,0,0 -- Template:Remain,t,link,flip
   while tdx<=length(tries) do
       for flipbits=1 to power(2,n)-1 do
           {remain,t} = tries[tdx]
           sequence flip = int_to_bits(flipbits,n)
           for timer=1 to n do
               if flip[timer] then
                   remain[timer] = eggtimers[timer]-remain[timer]
               end if
           end for
           integer mr = min(filter(remain,">",0))
           remain = sq_max(sq_sub(remain,mr),0)
           mr += t
           tries = append(tries,{remain,mr,tdx,flipbits})
           pdx = tdx
           while pdx do
               mr -= tries[pdx][2]
               if mr>=target then
                   if mr>target then exit end if
                   print_solution(eggtimers, tries, target, pdx)
                   return
               end if  
               mr += tries[pdx][2]
               pdx = tries[pdx][3]
           end while
       end for
       tdx += 1
       -- totally arbitrary sanity crash:
       if length(tries)>20000 then crash("no solution") end if
   end while

end procedure solve({4,7},9) solve({4,7},15) solve({5,7,31},36) -- (slightly better output than Julia, I think...) solve({4,5},7) -- (logo solution stops timer at t=12, this manages t=11) solve({7,11},15) -- (logo solution stops timer at t=22, this manages t=15) solve({5,8},14) -- (logo solution stops timer at t=24, this manages t=19)</lang>

Output:

Solution for 9 minutes with 4 and 7 minute eggtimers:
start timer
At t=0, flip 4 and 7, then when 4 runs out (leaving 3 in 7)...
At t=4, flip 4, then when 7 runs out (leaving 1 in 4)...
At t=7, flip 7, then when 4 runs out (leaving 6 in 7)...
At t=8, flip 7 (leaving 1), then when 7 runs out...
At t=9, stop timer

Solution for 15 minutes with 4 and 7 minute eggtimers:
start timer
At t=0, flip 4, then when 4 runs out...
At t=4, flip 4, then when 4 runs out...
At t=8, flip 7, then when 7 runs out...
At t=15, stop timer

Solution for 36 minutes with 5, 7 and 31 minute eggtimers:
start timer
At t=0, flip 5, then when 5 runs out...
At t=5, flip 31, then when 31 runs out...
At t=36, stop timer

Solution for 7 minutes with 4 and 5 minute eggtimers:
At t=0, flip 4 and 5, then when 4 runs out (leaving 1 in 5)...
start timer
At t=4, flip 4, then when 5 runs out (leaving 3 in 4)...
At t=5, flip 4 (leaving 1), then when 4 runs out...
At t=6, flip 5, then when 5 runs out...
At t=11, stop timer

Solution for 15 minutes with 7 and 11 minute eggtimers:
start timer
At t=0, flip 7 and 11, then when 7 runs out (leaving 4 in 11)...
At t=7, flip 7, then when 11 runs out (leaving 3 in 7)...
At t=11, flip 7 (leaving 4), then when 7 runs out...
At t=15, stop timer

Solution for 14 minutes with 5 and 8 minute eggtimers:
At t=0, flip 5 and 8, then when 5 runs out (leaving 3 in 8)...
start timer
At t=5, flip 5, then when 8 runs out (leaving 2 in 5)...
At t=8, flip 5 (leaving 3), then when 5 runs out...
At t=11, flip 8, then when 8 runs out...
At t=19, stop timer

Logo

tested with FMSlogo <lang logo> to bb Make "small_capacity 4 Make "big_capacity 7 make "small 0 make "big 0 make "t 0 print "_____________decision_0_game_over print "_________decision_1_start_timing print "_______decision_2_flip_small print "____decision_3_flip_big print "__decision_4_flip_both print "_________any_other_number________________wait do.until [show list list :small :big :t print "your_decision_0_1_2_3_4 human_decision if :my_decision>1 [machine_computes] ] [:my_decision=0] print list :t "minutes_passed end

to human_decision make "my_decision readword if :my_decision=1 [print "reset_timer make "t 0] if :my_decision=2 [print "flip_small make "small :small_capacity-:small] if :my_decision=3 [print "flip_big make "big :big_capacity-:big] if :my_decision=4 [print "flip_both make "small :small_capacity-:small make "big :big_capacity-:big ] if :my_decision>4 [print "wait] end

to machine_computes ifelse :small>:big [make "my_selection :big] [make "my_selection :small] if :small=0 [make "my_selection :big] if :big=0 [make "my_selection :small] make "small :small-:my_selection make "big :big-:my_selection make "t :t+:my_selection if :small<0 [make "small 0] if :big<0 [make "big 0] end

to zzz

A. 7 minutes with 4- and 5-minute timers

B. 15 minutes with 7- and 11-minute timers

C. 14 minutes with 5- and 8-minute timers

ifelse YesNoBox [Welcome] [run / show me the code] [bb] [edall]

A is possible

Turn both the 5 and the 4. When the 4 runs out, flip it over.Now, when the 5 runs out, start timing. The 4 will run for three more minutes, after which, you can flip it over to reach 7.

B is possible

Turn both the 7 and the 11. When the 7 runs out, start timing. The 11 will run for 4 more minutes, after which it can be flipped to reach 15.

C is possible

Turn both the 5 and the 8. When the 5 runs out, flip it. The 8 will then run out after 3 minutes, leaving 2 minutes in the 5. Flip the 8 then. When the 5 runs out, start timing. There are now 6 minutes left in the 8, and flipping the 8 after those 6 minutes gives 6 + 8 = 14 minutes.

end

Make "big 0 Make "big_capacity 5 Make "my_decision " Make "my_selection 4 Make "small 0 Make "small_capacity 4 Make "startup [zzz] Make "t 0

</lang>

Python

There isn't much of a task description as I write this, but, here goes...

<lang python>def hourglass_puzzle():

   t4 = 0
   while t4 < 10_000:
       t7_left = 7 - t4 % 7
       if t7_left == 9 - 4:
           break
       t4 += 4
   else:
       print('Not found')
       return 
   print(f"""

Turn over both hour glasses at the same time and continue flipping them each when they individually run down until the 4 hour glass is flipped {t4//4} times, wherupon the 7 hour glass is immediately placed on its side with {t7_left} hours of sand in it. You can measure 9 hours by flipping the 4 hour glass once, then flipping the remaining sand in the 7 hour glass when the 4 hour glass ends.

""")

hourglass_puzzle()</lang>

Output:

Turn over both hour glasses at the same time and continue flipping them each
when they individually run down until the 4 hour glass is flipped 4 times,
wherupon the 7 hour glass is immediately placed on its side with 5 hours 
of sand in it.
You can measure 9 hours by flipping the 4 hour glass once, then
flipping the remaining sand in the 7 hour glass when the 4 hour glass ends.

Raku

<lang perl6># 20201230 Raku programming solution

my @hourglasses = 4, 7; my $target = 9; my @output = []; my %elapsed = 0 => 1 ; my $done = False ;

for 1 .. ∞ -> $t {

  my $flip-happened = False;
  for @hourglasses -> $hg {
     unless $t % $hg {
        %elapsed{$t} = 1 unless %elapsed{$t};
        with @output[$t] { $_ ~= "\t, flip hourglass $hg " } else {
           $_ = "At time t = $t , flip hourglass $hg" }
        $flip-happened = True
     }
  }
  if $flip-happened {
     for %elapsed.keys.sort -> $t1 {
        if ($t - $t1) == $target {
           @output[$t1] ~= "\tbegin = 0";
           @output[$t]  ~= "\tend   = $target";
           $done = True
        }
        %elapsed{$t} = 1 unless %elapsed{$t} ;
     }
  }
  last if $done

}

.say if .defined for @output</lang>

Output:

At time t = 4 , flip hourglass 4
At time t = 7 , flip hourglass 7        begin = 0
At time t = 8 , flip hourglass 4
At time t = 12 , flip hourglass 4
At time t = 14 , flip hourglass 7
At time t = 16 , flip hourglass 4       end   = 9

REXX

This example is incomplete. Output does not show numbers? Please ensure that it meets all task requirements and remove this message.

Translation of: Python

<lang rexx>/*REXX program determines if there is a solution to measure 9 minutes using a */ /*──────────────────────────────────── four and seven minute sandglasses. */ t4= 0 mx= 10000

          do t4=0  by 4  to mx
          t7_left= 7   -   t4 % 7
          if t7_left==9-4  then leave
          end   /*t4*/

say if t4>mx then do

              say 'Not found.'
              exit 4
              end

say "Turn over both sandglasses (at the same time) and continue" say "flipping them each when the sandglasses individually run down" say "until the four-minute glass is flipped {t4//4} times," say "whereupon the seven-minute glass is immediately placed on its" say "side with {t7_left} minutes of sand in it." say say "You can measure 9 minutes by flipping the four-minute glass" say "once, then flipping the remaining sand in the seven-minute" say "glass when the four-minute glass ends." say exit 0</lang>

output   when using the internal default input:

Turn over both sandglasses  (at the same time)  and continue
flipping them each when the sandglasses individually run down
until the four-minute glass is flipped  {t4//4}  times,
whereupon the seven-minute glass is immediately placed on its
side with  {t7_left}  minutes of sand in it.

You can measure 9 minutes by flipping the four-minute glass
once,  then flipping the remaining sand in the seven-minute
glass when the four-minute glass ends.

Wren

Translation of: Julia

Library: Wren-math

<lang ecmascript>import "/math" for Nums

var hourglassFlipper = Fn.new { |hourglasses, target|

   var flippers = hourglasses.toList
   var series = []
   for (iter in 0...10000) {
       var n = Nums.min(flippers)
       series.add(n)
       for (i in 0...flippers.count) flippers[i] = flippers[i] - n
       var i = 0
       for (flipper in flippers) {
           if (flipper == 0) flippers[i] = hourglasses[i]
           i = i + 1
       }
       for (start in series.count-1..0) {
           if (Nums.sum(series[start..-1]) == target) return [start, series]
       }
   }
   Fiber.abort("Unable to find an answer within 10,000 iterations.")

}

System.write("Flip an hourglass every time it runs out of grains, ") System.print("and note the interval in time.") var tests = [ [[4, 7], 9], [[5, 7, 31], 36] ] for (test in tests) {

   var hourglasses = test[0]
   var target = test[1]
   var res = hourglassFlipper.call(hourglasses, target)
   var start = res[0]
   var series = res[1]
   var end = series.count - 1
   System.print("\nSeries: %(series)")
   System.write("Use hourglasses from indices %(start) to %(end) (inclusive) to sum ")
   System.print("%(target) using %(hourglasses)")

}</lang>

Output:

Flip an hourglass every time it runs out of grains, and note the interval in time.

Series: [4, 3, 1, 4, 2, 2]
Use hourglasses from indices 2 to 5 (inclusive) to sum 9 using [4, 7]

Series: [5, 2, 3, 4, 1, 5, 1, 4, 3, 2, 1, 4, 5, 2, 3, 4, 1]
Use hourglasses from indices 4 to 16 (inclusive) to sum 36 using [5, 7, 31]