Hourglass puzzle: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 365: Line 365:


</lang>
</lang>

=={{header|Nim}}==
{{trans|Wren}}
<lang Nim>import math, strutils

func hourglassFlipper(hourglasses: openArray[int];
target: int): tuple[start: int; series: seq[int]] =
var flippers = @hourglasses
for _ in 0..10_000:
let n = min(flippers)
result.series.add n
for i in 0..flippers.high:
dec flippers[i], n
if flippers[i] == 0: flippers[i] = hourglasses[i]
result.start = result.series.high
while result.start >= 0:
if sum(result.series[result.start..^1]) == target: return
dec result.start
raise newException(ValueError, "Unable to find an answer within 10_000 iterations.")


echo "Flip an hourglass every time it runs out of grains, "
echo "and note the interval in time."
const Tests = [(@[4, 7], 9), (@[5, 7, 31], 36)]
for test in Tests:
let
hourglasses = test[0]
target = test[1]
(start, series) = hourglassFlipper(hourglasses, target)
`end` = series.high
echo "\nSeries: ", series.join(" ")
echo "Use hourglasses from indices $1 to $2 (inclusive) to sum ".format(start, `end`),
"$1 using $2.".format(target, hourglasses.join(" "))</lang>

{{out}}
<pre>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.</pre>


=={{header|Python}}==
=={{header|Python}}==

Revision as of 20:21, 23 June 2021

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]

Perl

Flip each hourglass when it runs out and note the time for each. <lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Hourglass_puzzle use warnings;

findinterval( $_, 4, 7 ) for 1 .. 20;

sub findinterval 

 {
 my ($want, $hour1, $hour2) = @_;
 local $_ = (('1' | ' ' x $hour1) x $hour2 | ('2' | ' ' x $hour2) x $hour1) x $want;
 print /(?=\d).{$want}(?=\d)/
   ? "To get $want minute@{[$want == 1 ?  : 's'
     ]}, Start at time $-[0] and End at time $+[0]\n"
   : "$want is not possible\n";
 }</lang>
Output:
To get 1 minute, Start at time 7 and End at time 8
To get 2 minutes, Start at time 12 and End at time 14
To get 3 minutes, Start at time 4 and End at time 7
To get 4 minutes, Start at time 0 and End at time 4
To get 5 minutes, Start at time 7 and End at time 12
To get 6 minutes, Start at time 8 and End at time 14
To get 7 minutes, Start at time 0 and End at time 7
To get 8 minutes, Start at time 0 and End at time 8
To get 9 minutes, Start at time 7 and End at time 16
To get 10 minutes, Start at time 4 and End at time 14
To get 11 minutes, Start at time 21 and End at time 32
To get 12 minutes, Start at time 0 and End at time 12
To get 13 minutes, Start at time 7 and End at time 20
To get 14 minutes, Start at time 0 and End at time 14
To get 15 minutes, Start at time 20 and End at time 35
To get 16 minutes, Start at time 0 and End at time 16
To get 17 minutes, Start at time 4 and End at time 21
To get 18 minutes, Start at time 14 and End at time 32
To get 19 minutes, Start at time 16 and End at time 35
To get 20 minutes, Start at time 0 and End at time 20

Phix

<lang Phix>-- demo\rosetta\Hourglass_puzzle.exw 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

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>

Nim

Translation of: Wren

<lang Nim>import math, strutils

func hourglassFlipper(hourglasses: openArray[int]; 

                     target: int): tuple[start: int; series: seq[int]] =
 var flippers = @hourglasses
 for _ in 0..10_000:
   let n = min(flippers)
   result.series.add n
   for i in 0..flippers.high:
     dec flippers[i], n
     if flippers[i] == 0: flippers[i] = hourglasses[i]
   result.start = result.series.high
   while result.start >= 0:
     if sum(result.series[result.start..^1]) == target: return
     dec result.start
 raise newException(ValueError, "Unable to find an answer within 10_000 iterations.")


echo "Flip an hourglass every time it runs out of grains, " echo "and note the interval in time." const Tests = [(@[4, 7], 9), (@[5, 7, 31], 36)] for test in Tests: 

 let
   hourglasses = test[0]
   target = test[1]
   (start, series) = hourglassFlipper(hourglasses, target)
   `end` = series.high
 echo "\nSeries: ", series.join(" ")
 echo "Use hourglasses from indices $1 to $2 (inclusive) to sum ".format(start, `end`),
      "$1 using $2.".format(target, hourglasses.join(" "))</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.

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

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  4  times,
whereupon the seven-minute glass is immediately placed on its
side with  5  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]
Retrieved from "https://rosettacode.org/wiki/Hourglass_puzzle?oldid=305943"