Negative Sleep (#87)

The three rules of Ruby Q.:

  1. Please do not post any solutions or spoiler discussion for this quiz
    until
    48 hours have passed from the time on this message.

  2. Support Ruby Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. follow the discussion. Please reply to the original quiz
message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by MenTaLguY

(Inspired by recent insomnia and a #ruby-lang snippet on Anarchaia…)

Let’s suppose there existed a sleep which accepted negative arguments.
Would it
actually imply time travel? In the case of a negative argument, the
obvious
description of sleep’s behavior (halt the thread for the given minimum
number of
seconds) would be trivially satisfied by behaving as if sleep(0) had
been
called. That’s not a very interesting result.

Of course, that’s not the only way to define sleep. You could also view
a sleep
as specifying the relationship between the computations on either side
of it.
In that case, sleep(1) might request that the second computation begin
at least
a second after the completion of the first one. Negative sleeps would
simply
reverse the order of the two computations, sleep(-1) meaning that the
first
computation should begin at least a second after the completion of the
second.

That sounds slightly impossible to implement, doesn’t it? But consider
something like this:

( Computation.new { ... } + Sleep.new(-1) + Computation.new { ... } 

).run

Another possible definition for sleep would be a minimum delta time
between the
end of the first computation and the beginning of the second one. In
that case,
the implementation of sleep would have to ensure that the second
computation
above would begin executing no less than one second before the
completion of the
first one. Multiple threads (and the ability to predict or control a
computation’s duration) might prove useful.

Your assignment for this quiz is twofold:

1) Devise an "interesting" definition for sleep which allows negative
   durations.  Alternately, use one of the definitions given here.
2) Write some Ruby code demonstrating behavior which satisfies that
   definition.  As with the above example, you needn't provide a 

drop-in
replacement for Kernel.sleep.

If your solution does involve time travel, please ensure that it isn’t
posted
before the end of the 48-hour spoiler period (or before the beginning of
the
quiz).

On Jul 14, 2006, at 10:10 AM, Morton G. wrote:

I know that the Sokoban quiz was posted a long time ago. But I
didn’t even know that Ruby existed back then. I first heard about
Ruby and became interested it in April of this year. In June, I
picked up Best of Ruby Q… It was from that book that I learned
about the Sokoban quiz.

Welcome to Ruby, Morton, and thanks for sharing your code with us! :wink:

James Edward G. II

As I was suffering from insomnia I had to try to solve this one :wink:
Please find my solution attached.

Cheers
Robert

i’d like to see more of these quizes :slight_smile:
i think negative sleep means insomnia…
insomnia builds up until one sleeps, so i figure it works this way:

irb(main):001:0> sleep(-5)
=> -5
irb(main):002:0> sleep(6)

  • 1 second later *
    => true

so my solution looks like this:

#------------------

alias :old_sleep :sleep
$sleep=0

def sleep(n)
$sleep+=n
if $sleep>0
old_sleep($sleep)
$sleep=0
true
else
$sleep
end
end
#------------------

greetings, Dirk.

Here is one more solution to the Sokoban quiz. I think people might
be interested in seeing this one because 1) it uses a different
implementation strategy then the solutions posted back in 2004, and
2) it is somewhat more complete than those solutions.

I know that the Sokoban quiz was posted a long time ago. But I didn’t
even know that Ruby existed back then. I first heard about Ruby and
became interested it in April of this year. In June, I picked up Best
of Ruby Q… It was from that book that I learned about the Sokoban
quiz.

I had a lot of fun implementing Sokoban in Ruby. The only difficulty
I encountered was in dealing with the Curses module, for which l was
not able to locate up-to-date documentation. In the end, I had to
fall back on trial-and-error to get the code involving Curses methods
to work.

Regards, Morton

--------------------------- start of code ---------------------------

#! /usr/bin/ruby -w

Author: Morton G.

Date: July 13, 2006

An implementation of the Sokoban game based on the model-view-

controller

design pattern. It also avoids using case blocks, using hashes

instead.

The user interface is implemented with Curses. Games are saved and

restored using YAML.

require ‘curses’

WELCOME = ‘Welcome to Sokoban 1.0 – press h if you need help’

The SOKOBAN environment variable must be defined and point to the

folder

where the file “levels.txt” can be found. Further, any files

written out

(such as saved games, level maps, and completion certificates) will be

written to this folder.

FOLDER = ENV[‘SOKOBAN’]

LEVELS is the name of a file containing a collection of level maps

to be

loaded during start-up.

LEVELS = “levels.txt”

GAME is the name given to a saved game. If such a file exists in

FOLDER,

the game can be restored from it at any time during play.

GAME = “sokoban.yaml”

Unit vectors representing one-step moves in the four cardinal

directions.
UVEC = {
?e => [0, 1],
?w => [0, -1],
?n => [-1, 0],
?s => [1, 0]
}

A sokoban represents the warehouse worker. It knows the following

things:

Where it is

How to move around the level map

How to push crates

class Sokoban

# Transition table for simple moves.
MOVE_TABLE = {
   '@ ' => ' @',
   '@.' => ' +',
   '+ ' => '[email protected]',
   '+.' => '.+'
   }

# Transition table for crate-pushing moves.
PUSH_TABLE = {
   '@o ' => ' @o',
   '@o.' => ' @*',
   '@* ' => ' +o',
   '@*.' => ' +*',
   '+o ' => '[email protected]',
   '+o.' => '[email protected]*',
   '+* ' => '.+o',
   '+*.' => '.+*'
   }

# Given a level's map, return the position of the token representing
# the sokoban. When successful, returns an array of form [row, col];
# otherwise, it returns nil.
def Sokoban.find(level_map)
   level_map.each_with_index do |row, i|
      j = row.index(/[@+]/)
      return [i, j] if j
   end
   return nil
end

attr_reader :row, :col

# Argument position must be an array of the form [row, col].
def initialize(position)
   @row = position[0]
   @col = position[1]
end

# Perform a simple move; i.e., no crate push.
# Argument token must be is one of ?e, ?w, ?n, or ?s.
# Argument map must be a level map.
def move(token, map)
   dr, dc = UVEC[token]
   r, c = @row + dr, @col + dc
   old = map[@row][@col, 1] + map[r][c, 1]
   new = MOVE_TABLE[old]
   if new then
      rows = [@row, r]
      cols = [@col, c]
      @row = r
      @col = c
      return [rows, cols, old, new]
   else
      return [nil, nil, nil, nil]
   end
end

# Perform a crate-pushing move.
# Argument token must be is one of ?e, ?w, ?n, or ?s.
# Argument map must be a level map.
def push(token, map)
   dr, dc = UVEC[token]
   r, c = @row + dr, @col + dc
   rr, cc = r + dr, c + dc
   old = map[@row][@col, 1] + map[r][c, 1] + map[rr][cc, 1]
   new = PUSH_TABLE[old]
   if new then
      rows = [@row, r, rr]
      cols = [@col, c, cc]
      @row = r
      @col = c
      return [rows, cols, old, new]
   else
      return [nil, nil, nil, nil]
   end
end

def to_s
   "[#@row, #@col]"
end

end

A model represents the state of the level being played. It

maintains the

level map and knows the following things:

What moves are valid

When a level is complete

How to perform valid moves

How to undo previous moves

class Model

PASS   = ' '   # marks empty passage cell
EMPTY  = '.'   # marks empty storage cell
CRATE  = 'o'   # marks crate in pasaage cell
FILLED = '*'   # marks crate in storage cell

# The collection of level maps.
# Levels are 1-based, so level 0 is just a place holder and is

not used.
@@maps = [’#’]

# Load a collection of Sokoban level maps from the specified path.
def Model.load_maps(path)
   File.open(path, "r") do |f|
      map = []
      f.each_line do |line|
         if line =~ /^\s*#/ then
            map << line.chomp
         elsif ! map.empty? then
            @@maps << map
            map = []
         end
      end
      @@maps << map unless map.empty?
   end
end

# Returns the number of levels available for play.
def Model.levels
   @@maps.length - 1
end

attr_reader :map, :rows, :cols, :sokoban, :moves_made

# Argument level must be an integer in range 1..Model.levels.
def initialize(level)
   @level = level
   @moves_made = 0
   @history = []
   # Need a deep copy because it will be destructively modified

during
# game play.
@map = @@maps[@level].collect {|r| String.new®}
@rows = @map.length
@cols = (@map.collect {|r| r.length}).max
@sokoban = Sokoban.new(Sokoban.find(@map))
end

# Returns true if the move is valid and false if it is not. A

valid move
# produces the appropriate change in the level’s map.
# Game moves are represented by single character tokens (?e, ?w, ?
n, ?s)
# indicating the direction of the move.
def move(token)
dr, dc = UVEC[token]
adjacent = @map[@sokoban.row + dr][@sokoban.col + dc, 1]
if adjacent == PASS || adjacent == EMPTY then
rows, cols, old, new = @sokoban.move(token, @map)
elsif adjacent == CRATE || adjacent == FILLED then
rows, cols, old, new = @sokoban.push(token, @map)
else
return false
end
return false unless new
# Move is valid, so update the level map.
rows.length.times do |k|
map_row = @map[rows[k]]
map_row[cols[k]] = new[k]
end
# Update the undo history.
@history << [rows, cols, old]
@moves_made = @history.length
return true
end

# Complete undo is simple to implement, but rather memory intensive.
def undo
   return false if @history.empty?
   rows, cols, old = @history.pop
   rows.length.times do |k|
      map_row = @map[rows[k]]
      map_row[cols[k]] = old[k]
   end
   @moves_made = @history.length
   @sokoban = Sokoban.new([rows[0], cols[0]])
   return true
end

# The level is complete when the level map contains no crate tokens.
def level_complete?
   crates = @map.collect do |row|
      row.include?(CRATE)
   end
   ! crates.any?
end

end

A view knows how to draw a visual representation of the level being

played.
class View

include Curses

# A view must be initialized with an instance of Model.
def initialize(model)
   @model = model
   # The spaces needed on the left side of level's map to center it.
   @left_margin =  ' '* ((cols - @model.cols) / 2)
   # Put four blank lines before the top line of the level's map.
   @top_margin = 4
end

# Draw the level's map in the screen buffer.
def draw
   @model.map.each_with_index do |row, i|
      setpos(@top_margin + i, 0)
      addstr(@left_margin + row)
   end
end

end

Provide a Curses-based approximation to the alert box widgets provided

by GUIs. Somewhat crude but useful as well as easy to use.

class AlertBox < Curses::Window

# Aids in determining the size of an alert's frame.
# Returns the height and width of a frame will closely fit the
# specified text. Provides for a border and left and right margins.
def AlertBox.size(text)
   text = text.split("\n")
   [text.length + 2, (text.map {|m| m.length}).max + 6]
end

# Aids in centering an alert on the screen.
# Returns a frame that will closely fit the specified text. Provides
# for a border and left and right margins.
def AlertBox.center(text)
   h, w = size(text)
   [(Curses::lines - h) / 2, (Curses::cols - w) / 2, h, w]
end

# rect is the alert's frame, an array of the form [top_row, top_col,
# heigth, width].
# text is the alert's content, a string consisting of one or more
# lines.
def initialize(rect, text)
   @top_y = rect[0]
   @top_x = rect[1]
   @height = rect[2]
   @width = rect[3]
   @text = text.split("\n")
   super(@height, @width, @top_y, @top_x)
   box(?#, ?#, ?#)
end

# Display the alert on the screen.
def show
   @text.length.times do |i|
      setpos(i + 1, 3)
      addstr(@text[i])
   end
   refresh
end

RESULT = {?y => true, ?n => false}

# Display the alert and wait for a key press.
# Return true if the user preses y.
# Return false if the user presses n.
# Beep on any other keystrokes.
def ask_y_or_n
   show
   Curses::noecho
   key_chr = nil
   loop do
      key_chr = getch
      break if key_chr == ?y || key_chr == ?n
      Curses::beep
   end
   Curses::echo
   RESULT[key_chr]
end

end

A controller gets the player’s keystrokes and translates them in to

game

actions.

class Controller

require 'yaml'
include Curses

# Keystroke command dispatch table
DISPATCH = Hash.new(:beep)

# general commands
DISPATCH[?A]         = :abort       # abort
DISPATCH[?h]         = :key_help    # show help
DISPATCH[?l]         = :new_level   # change level
DISPATCH[?m]         = :map_help    # show map legend & sokoban

position
DISPATCH[?n] = :up_level # advance to next level
DISPATCH[?p] = :dn_level # return to previous level
DISPATCH[?q] = :quit # quit
DISPATCH[?r] = :restore # restore game
DISPATCH[?s] = :save # save game
DISPATCH[?w] = :write_map # write map to file

# movement
DISPATCH[Key::RIGHT] = :go_east     # right arrow = one step east
DISPATCH[Key::LEFT]  = :go_west     # left arrow = one step west
DISPATCH[Key::UP]    = :go_north    # up arrow = one step north
DISPATCH[Key::DOWN]  = :go_south    # down arrow = one step south
DISPATCH[?z]         = :undo        # undo previous move

def initialize
   unless FOLDER then
      puts "SOKOBAN environment variable not set"
      exit(false)
   end
   map_file = FOLDER + LEVELS
   if File.exists?(map_file) then
      Model.load_maps(map_file)
   else
      puts "Can't find Sokoban levels file"
      exit(false)
   end
   init_screen
   begin
      cbreak
      stdscr.keypad(true)
      @command_line = lines - 1
      @status_line = lines - 2
      @level = 1
      @model = Model.new(@level)
      @view = View.new(@model)
      @key_chr = nil
      say(WELCOME)
      run
   ensure
      close_screen
      puts $debug unless $debug.empty?
   end
end

# Command ask-and-dispatch loop
def run
   catch(:game_over) do
      loop do
         @view.draw
         ask_cmd
         send(DISPATCH[@key_chr])
      end
   end
end

# Handle request to abort -- exit immediately without reminding tihe
# user to save.
def abort
   throw(:game_over)
end

SAVE_ALERT = <<TXT
Do you want to save your game before you quit?

Press y to save
Press n to quit without saving
TXT

# Handle request to quit -- befoe exiting, remind tihe user to save.
def quit
   alert = AlertBox.new(AlertBox.center(SAVE_ALERT), SAVE_ALERT)
   save if alert.ask_y_or_n
   throw(:game_over)
end

KEY_INFO = <<INFO
Sokoban keystroke commands

General commands
A immediate quit
h display this message
l go to another level – you will
be asked for the level number
m show legend for level map
n go to next level
p go to previous level
q quit – you will be asked to save
r restore saved game
s save game to disk
w write level map to disk

Movement commands
Right-arrow move one step east
Left-arrow move one step west
Up-arrow move one step north
Down-arrow move one step south
z undo previous move

Press any key to dismiss
INFO

# Handle request for infomation on keystroke commands.
def key_help
   alert = AlertBox.new(AlertBox.center(KEY_INFO), KEY_INFO)
   alert.show
   ask_cmd
   clear
end

MAP_INFO = <<INFO
Sokoban map symbols

@ sokoban (warehouse worker)

  • sokban on storage bin

. empty storage bin
o crate needing to be stored

  • crate stored in a bin

wall or other obstacle

Press any key to dismiss
INFO

# Handle request for infomation on map symbols.
def map_help
   say("Sokoban is at #{@model.sokoban}")
   alert = AlertBox.new(AlertBox.center(MAP_INFO), MAP_INFO)
   alert.show
   ask_cmd
   clear
end

# Handle request to change to another level.
def new_level
   current = @level
   msg = ask_level
   if @level == current then
      say(msg)
   else
      set_level(msg)
   end
end

# Handle request to go to the next level.
def up_level
   nxt = @level + 1
   if nxt > Model.levels then
      beep
   else
      @level = nxt
      set_level("Starting level #@level")
   end
end

# Handle request to go to the previous level.
def dn_level
   nxt = @level - 1
   if nxt < 1 then
      beep
   else
      @level = nxt
      set_level("Starting level #@level")
   end
end

# Change to the requested level.
def set_level(msg)
   @model = Model.new(@level)
   @view = View.new(@model)
   clear
   say(msg)
end

# Handle request to write the current level map out to disk.
# The level map is written to FOLDER. The file name is generated

from
# the current level and the number of moves made. For example, if
a map
# is written out for level 3 at move 117, the map file is named
# “level_map.3.117.txt”.
def write_map
path = FOLDER + “level_map.#@level.#{@model.moves_made}.txt”
text =
“Level: #@level\nMove: #{@model.moves_made}\n\n” +
@model.map.join("\n")
File.open(path, ‘w’) {|f| f.write(text)}
say(“Level map written to disk”)
end

# Handle request to save the current state of game to a YAML file

from
# which it can be restored at some later time.
def save
game_file = FOLDER + GAME
game = {‘level’ => @level, ‘model’ => @model}
File.open(game_file, ‘w’) do |f|
YAML.dump(game, f)
say(“Game saved to disk”)
end
end

# Handle request to restore a game from a YAML file.
def restore
   game_file = FOLDER + GAME
   if File.exists?(game_file) then
      game = YAML.load_file(game_file)
      @level = game['level']
      @model = game['model']
      @view = View.new(@model)
      clear
      say("Game restored from disk")
   else
      say("Cant find game file on disk")
   end
end

# Handle request to move eastward.
def go_east
   go(?e, "Moved east")
end

# Handle request to move westward.
def go_west
   go(?w, "Moved west")
end

# Handle request to move northward.
def go_north
   go(?n, "Moved north")
end

# Handle request to move southward.
def go_south
   go(?s, "Moved south")
end

CERTIFICATE_ALERT = <<TXT
Level Completed

You qualify for a certificate to commemorate your success

Press y to have the certificate issued
Press n to skip the certificate
TXT

# Ask the model to move the sokoban in the direction indicated by

token.
# if move succeeded, check for level completion.
def go(token, msg)
if @model.move(token) then
if @model.level_complete? then
@view.draw
say(“Congratulations! You have completed level #@level”)
alert = AlertBox.new(AlertBox.center(CERTIFICATE_ALERT),
CERTIFICATE_ALERT)
write_certificate if alert.ask_y_or_n
clear
up_level
else
say(msg)
end
else
beep
end
end

# Ask the model to undo the sokoban's last move. Decrement the

move count
# if successful.
def undo
if @model.undo then
say(“Undid move #{@model.moves_made + 1}”)
else
beep
end
end

# Display a message on the status line. The message will be

prefixed by
# the level number and the move count.
def say(text)
text = "Level #@level, move #{@model.moves_made}: " + text
setpos(@status_line, 0)
addstr(text.ljust(cols))
refresh
end

# Display a prompt for imput on the command line.
# Return the user's response (a string).
def ask_str(prompt)
   w = prompt.length
   setpos(@command_line, 0)
   addstr(prompt.ljust(cols))
   setpos(@command_line, w)
   refresh
   getstr
end

COMMAND_PROMPT = '>> '
CURSOR_COLUMN = COMMAND_PROMPT.length

# Prompt for and get a keystroke command.
def ask_cmd
   setpos(@command_line, 0)
   addstr(COMMAND_PROMPT.ljust(cols))
   setpos(@command_line, CURSOR_COLUMN)
   refresh
   noecho
   @key_chr = getch
   echo
end

LEVEL_PROMPT = "What level do you want to play? "

# Ask the user for a level number. If the response is valid,

accept it;
# if not, the current level persists.
def ask_level
prompt = LEVEL_PROMPT + "[1 - #{Model.levels}]: "
begin
response = ask_str(prompt).to_i
if (1…Model.levels).include?(response) then
@level = response
msg = “Starting level #@level
else
raise RangeError
end
rescue
# Resume current level.
msg = “Level change cancelled”
end
return msg
end

# Write a certificate of completion for the current level out to

disk.
# The certificate is written to FOLDER. The file name is
generated from
# the USER environment variable, the current level, and the
number of
# moves it took to complete the level. For example, if user “mg”
# completes leve 3 in 435 moves, the certificate file is named
# “mg.3.435.txt”. The file’s contents repeat the information
contained
# in the file name in a more readable format and adds the date.
def write_certificate
user = ENV[‘USER’]
date = Time.now.strftime("%d/%m/%Y")
path = FOLDER + “#{user}.#@level.#{@model.moves_made}.txt”
text = <<-TXT
Sokoban Certificate of Completiion
----------------------------------
Date: #{date}
Level: #@level
Moves: #{@model.moves_made}
Player: #{user}
TXT
text.gsub!(/^\s+/, ‘’)
File.open(path, ‘w’) {|f| f.write(text)}
end

end

$debug = []
Controller.new

--------------------------- end of code ---------------------------

“Let’s suppose there existed a sleep which accepted negative
arguments. Would it actually imply time travel?”

…Well of course! I created the SuperSleep class, which when given a
negative argument jumps backwards into the history of execution by
the amount of time specified and resumes execution from that point.

So, the program that looks like this:


tta = TwistyTimeApp.new([Computation.new("x = 0 "),
Computation.new("p x "),
Computation.new("x += 1 "),
Computation.new("p x "),
Computation.new("x += 1 "),
Computation.new("p x "),
Computation.new("x += 1 "),
Computation.new("p x "),
SuperSleep.new(-0.015),
SuperSleep.new(-0.015)])
tta.run


Would have output that might look like this (comments added for
clarification of flow):

0
1
2
3 #reaches the first SuperSleep, jumps back .015 seconds
4 #gets to the third Computation, starts flowing again
5
6 #gets to the second SuperSleep, jumps back .015 seconds
0 #reaches the first Computation (resetting x), and starts flowing again
1
2
3

Wacky, huh?!

Caveats:

  • When a SuperSleep is executed (possibly jumping back in time) it
    is also destroyed, so that no infinite loops are created (jump back,
    flow forward, jump back, etc. etc.)
  • The time at which each Computation is executed is set once, the
    first time it happens. This might change later, if I want to make
    things really confusing.
  • SuperSleeps with positive delta just sleep for that long, instead
    of jumping forward into the future. This is definitely going to
    change, so that they actually jump forward in the execution by the
    amount of time specified, skipping certain Computations :).
  • If a Negative Sleep goes past the beginning of the program, it
    simply starts over without accounting for the extra time by which it
    surpassed the beginning of execution.

THE FUTURE:

  • I’m hoping to make this program continuations/generator based.
    Expect that later tonight I guess.
  • Jumping into the future with SuperSleeps given positive numbers,
    instead of just sleeping! :slight_smile:

Attached is my code, check it out and let me know what you think!
(Run it a few times to get an idea of how the output can change, and
adjust the sleeps for the speed of your computer :P)


Well, as everybody are sending in solutions here are mines …

The first one (sleep1.rb) simply takes the computations, order them, and
consider the time to sleep is between the end of the previous and the
beginning of the next.

The second one (sleep3.rb) takes the same arguments but sleep according
to the beginning time of each set of operations. All the operations
supposed to begin at the same time will happen in the order they were
defined (i.e. we have one thread per beginning)

At last, the third one (sleep4.rb) uses one thread per computation,
hence there is no predictability in the order of computation for
operations which are suppose to begin at the same time.

Attached also, a test file … just change the require to test each
module.

Pierre

Just something little I whipped up!
class TimeTravelProc < Proc
attr_accessor :sleep
def initialize(*args,&block)
@sleep = 0
super(*args,&block)
end
end
class TimeTravelArray < Array
def +(o)
TimeTravelProc === o ? push(o) : Integer === o ? last.sleep = o :
raise;self
end
def sort
sort_by{|p|p.sleep}
end
def run
sort.map{|x|x[]}
end
end
class Integer
def sleep
self
end
end
t = TimeTravelArray.new
t2=TimeTravelProc.new{print “Second\n”}
t3=TimeTravelProc.new{print “First\n”}
t4=TimeTravelProc.new{print “last\n”}
t + t4 + -1.sleep + t3 + -3.sleep + t2 + -2.sleep
t.run

j`ey
http://www.eachmapinject.com

On 7/16/06, Pierre Barbier de Reuille <

Hi there, Ruby Q.! Nice to meet you. It’s my first time here, so don’t
be too
rude with me :smiley:

Err… well… here is my solution to the negative sleep issue.
I’ve been highly inspired by MenTaLguY’s

( Computation.new { ... } + Sleep.new(-1) + Computation.new { ... } 

).run

It executes the second computation one second before the first.
But I thought the code was a bit redundant. Ruby already has a
“Computation”-thing, doesn’t it?
I just extended Proc to be able to do something like:

(proc { ... } + ProcStack.sleep(-1) + proc { ... }).call

Looks cleaner IMO.

ProcStack.sleep(-1) returns more or less a “proc { sleep 1 }” with a
little meta-information appended which
informs our ProcStack-instance (created by Proc#+) that the sleep as
well as the following proc
should be executed before the previous proc. I hope you all
understood… my english isn’t the best
and even in my native language (german, btw) I suck at explaining
things.

Gah, just read the code. ^^

#-------------------------------------------------------------------------------

time machine, whee!

class NegativeProc < Proc; end
class ProcStack
def initialize(*args)
@negative = args.shift if args.first == true
@stack = args
end

def + code
new_stack = @stack.dup

if code.is_a? NegativeProc
  new_stack.insert(-2, code)
  new_stack.unshift(true)
elsif code.respond_to? 'call'
  if @negative
    new_stack.insert(-3, code)
  else
    new_stack.push(code)
  end
end

ProcStack.new(*new_stack)

end

def call
@stack.each { |p| p.call }
end

def ProcStack.sleep(time)
if time < 0
NegativeProc.new { Kernel.sleep(time.abs) }
else
Proc.new { Kernel.sleep(time) }
end
end
end

class Proc
def + code
ProcStack.new(self) + code
end
end

should print something like “chunky … bacon\hooray for foxes”

whee = proc { print “bacon\n” } + ProcStack.sleep(-2) + proc { print
"chunky " } +
ProcStack.sleep(1) +
proc { print "hooray for " } + proc { print “foxes” }
whee.call

#-------------------------------------------------------------------------------

Well… I know the solution has weaknesses and could be extended.
(This @negative-thingy is quite an ugly hack, but I don’t see a better
way ATM)
Also I have something like free movable code in my mind:

proc { omg } + proc(-1) { wtf } + proc(1) { bbq } + proc { lol }

which would evaluate to:

wtf; omg; lol; bbq

Would be funny to maintain such source, wouldn’t it?
But since the current code does all work asked for in the quiz I’m
satisfied with it.

~dingsi

You could also view a sleep as specifying the relationship between
the computations on either side of it. In that case, sleep(1) might
request that the second computation begin at least a second after
the completion of the first one. Negative sleeps would simply
reverse the order of the two computations, sleep(-1) meaning that
the first computation should begin at least a second after the
completion of the second.

Alright, I basically took that definition of negative sleep, although
I had to decide what should happen when there are three or more
statements separated by negative sleeps and what should happen if a
negative sleep is before after everything else. I decided both
arbitrarily.

I decided to implement it as a class that takes procs and runs them in
the right order, which I think came out pretty cleanly.


Mitchell Koch

#! /usr/bin/env ruby

Negative sleep via time machine

Author: Mitchell Koch

Definition of negative sleep: the statement after the sleep call is

run that many seconds before the statement before the call, meaning

that is equivalent to the order of the two statements as well as the

sign of the number of seconds to sleep both being inverted.

If there are three or more statements with negative sleeps between

them, they should be inverted two at a time from top to bottom.

Using negative sleep before or after everything else is called is

undefined and raises errors here.

class TimeMachine
def initialize
@statements = []
yield self
end

Give the machine something to do

def do(&proc)
@statements << proc
if @swapidx
if @swapidx < 0
# calling at beginning error
raise “Cannot warp time before anything else is called”
end
# swap the last statement and the one before the sleep call
@statements[-1], @statements[@swapidx] =
@statements[@swapidx], @statements[-1]
@swapidx = false
end
end

Define the time between two events

def sleep(n)
@swapidx = @statements.size-1 if n < 0
@statements << Proc.new { Kernel.sleep n.abs }
end

Activate the machine

def run
if @swapidx
# calling at end error
raise “Cannot warp time after everything else is called”
end
@statements.each { |s| s.call }
end
end

For minus one seconds,

wuh?

sleep…

TimeMachine.new do |t|
t.do { puts “sleep…” }
t.sleep -1
t.do { puts "For minus one seconds, " }
t.sleep -1
t.do { puts “wuh?” }
end.run

Your assignment for this quiz is twofold:

  1. Devise an “interesting” definition for sleep which allows negative
    durations. Alternately, use one of the definitions given here.

This is what negative sleep basically meant for me: if we are negative
sleeping, in relation to other threads, then do not wait for those other
threads to finish first. Very negative sleepers are very awake and
process more often as compared to not so negative sleepers. So a way to
think about this is a negative awake setting. With this in mind, this
seems like it is really the same as thread priority, set to the negative
of the sleep value.

I came to this by thinking about this in the approach of how sleep is
oftentimes used (to wait for other threads to complete) and thought
about what the opposite behavior should be.

Note: Like normally, other threads need to play nice and sleep sometimes
in order to allow other threads to process, and thusly to allow those
others to negative sleep as well.

  1. Write some Ruby code demonstrating behavior which satisfies that
    definition. As with the above example, you needn’t provide a
    drop-in
    replacement for Kernel.sleep.

module Kernel
def n_sleep(n_sleep_time)
Thread.current.priority = -n_sleep_time
end
end

test stuff

if FILE == $0
Thread.new { n_sleep(-3); 1.upto(10) {print “A”; sleep(0.1)} }
Thread.new { n_sleep( 1); 1.upto(10) {print “B”; sleep(0.1)} }
Thread.new { n_sleep(-2); 1.upto(10) {print “C”; sleep(0.1)} }
n_sleep(10); 1.upto(10) {print “m”; sleep(0.1)}
loop {break if Thread.list.size == 1}
end

Mitchell Koch wrote:

Alright, I basically took that definition of negative sleep, although
I had to decide what should happen when there are three or more
statements separated by negative sleeps and what should happen if a
negative sleep is before after everything else. I decided both
arbitrarily.

I decided to implement it as a class that takes procs and runs them in
the right order, which I think came out pretty cleanly.

[snip]

This has to be the most useless Ruby Q. I’ve ever seen.

I like it a lot.

Hal

Hi,

I tried to keep it simple. The code blocks in an Insomnia object are
assumed to be executed infinitely fast. Sleeping a negative amount means
that the following block is run before the preceding block.

Code blocks are stored in a hash where the key is the relative time
(@t) and the
value is an array of Proc objects. The run method simply sorts by
time and calls
the procs after sleeping (Kernel) the required number of seconds.

Cheers,
Boris

class Insomnia

It’s really sick to call this method ‘do’,

but I can’t think of a better name…

def do(&block)
@blocks[@t] << block
end

def sleep(seconds)
@t += seconds
end

def run
times = @blocks.keys.sort
t_now = times.min
times.each do |t|
Kernel.sleep(t - t_now)
t_now = t
@blocks[t].each {|b| b.call}
end
end

def initialize
@blocks = Hash.new {|h, t| h[t] = []}
@t = 0
yield(self)
run
end
end

Insomnia.new do |i|
i.do { puts “Something will explode in ten seconds:” }
i.sleep(10)
i.do { puts “Boom!” }

countdown:

1.upto(9) do |num|
i.sleep(-1)
i.do { puts num.to_s }
end
end

On Jul 17, 2006, at 1:16 PM, Pit C. wrote:

hacks it isn’t even necessary to invent a new syntax:
But now we all want to see the code so we are curios why you didn’t
submit it… :wink:

James Edward G. II

Ruby Q. schrieb:

(…)
That sounds slightly impossible to implement, doesn’t it? But consider
something like this:

( Computation.new { … } + Sleep.new(-1) + Computation.new { … } ).run

(…)

This is not a submission, I just wanted to show that with some evil
hacks it isn’t even necessary to invent a new syntax:

C:\tmp>type test-negative-sleep.rb
require “negative-sleep”

def log msg
where = caller[ 0 ]
time = Time.now.strftime “%H:%m:%S”
puts “#{where} #{time} #{msg}”
end

with_negative_sleep do
log “before”
sleep( -2 )
log “after”
end

C:\tmp>ruby test-negative-sleep.rb
test-negative-sleep.rb:12 20:07:42 after
test-negative-sleep.rb:10 20:07:44 before

C:\tmp>

Regards,
Pit

James Edward G. II schrieb:

But now we all want to see the code so we are curios why you didn’t
submit it… :wink:

Yeah, I think I shouldn’t have posted it, but I couldn’t resist to make
you curious :wink:

As I said, it really was a hack, written in a couple of minutes. In its
current form it is pretty useless. It makes use of some evil code I’m
still experimenting with. I first want to enhance the codebase before
I’ll publish it. This won’t happen before the end of August, though.

Regards,
Pit

On 7/18/06, Adam S. [email protected] wrote:

       replacement for Kernel.sleep.

inspecting core dumps and trace logs, going through my code line by
if RUBY_PLATFORM =~ /(win|w)32$/
TimeStrFormat = “time %H:%M:%S”
else
TimeStrFormat = “date -s %H:%M:%S”
end

Dangerous !!!
Just do not do this, you have to be root to do it anyway, but if you do
it
say good bye to your filesystems, databases etc. etc.

Would be nice to do it in a virtual host though :wink:

Cheers
Robert

sleep 5
p “the time is #{Time.now}”
sleep -50
p “the time is #{Time.now}”
sleep -50
p “the time is #{Time.now}”
end

-Adam


Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.

  • Albert Einstein

On 7/18/06, Robert D. [email protected] wrote:

On 7/18/06, Adam S. [email protected] wrote:

TimeStrFormat = "date -s %H:%M:%S"


system(t.strftime(TimeStrFormat))

Dangerous !!!
Just do not do this, you have to be root to do it anyway, but if you do it
say good bye to your filesystems, databases etc. etc.

oops. It’s been about 10 years since I used Unix regularly, and I was
never the sysadmin.

I suppose this is offtopic, but why would it mess up the filesystem?
I realize if you leave the time set in the past you’ll run into
problems with file creation/modification times, but the testscript
restores the time to its original point - where’s the lasting harm in
that?

I didn’t seem to suffer any permanent side effects after running it on
WinXP.

-Adam

On 7/14/06, Ruby Q. [email protected] wrote:

    1) Devise an "interesting" definition for sleep which allows negative
       durations.  Alternately, use one of the definitions given here.
    2) Write some Ruby code demonstrating behavior which satisfies that
       definition.  As with the above example, you needn't provide a drop-in
       replacement for Kernel.sleep.

When I read this quiz, it reminded me of the time I was working on a
huge realtime 24/7 distributed unix system. Each machine had a time
daemon keeping it in synch with a central time server. During the
first live tests, my application would occasionally core-dump. When I
first saw the traces, It looked like either one of my queues was
getting corrupted, or the system time had jumped backward. The lead
of the services group assured me that it was absolutely impossible
that the daemon could set the clock back. So I spent 2 long days
inspecting core dumps and trace logs, going through my code line by
line, adding more logging, questioning my sanity. In the end, I
presented the lead with a stack of logs proving that the time daemon
was infact occasionally setting the clock backward by one second.

That gave me this idea for how to implement negative sleep:

time_demon.rb

(only tested on windows)

module Time_Demon
if RUBY_PLATFORM =~ /(win|w)32$/
TimeStrFormat = “time %H:%M:%S”
else
TimeStrFormat = “date -s %H:%M:%S”
end

def sleep sec
t = Time.now
t+=sec
system(t.strftime(TimeStrFormat))
sec.to_i
end
end

if FILE == $0
p “the time is #{Time.now}”
sleep 5
p “the time is #{Time.now}”
begin
sleep -5
rescue Exception => ex
p “caught >>#{ex}<<”
end
p “the time is #{Time.now}”

include Time_Demon
sleep 100
p “the time is #{Time.now}”
sleep -50
p “the time is #{Time.now}”
sleep -50
p “the time is #{Time.now}”
end

-Adam

I took the concept of negative sleeping as guaranteeing that the
thread will not sleep or relinquish control for that time period.
Normal sleep means that the thread concedes to the other threads of
the program for the specified time, so negative sleeping is forcing
all other threads to concede control to the current thread for the
specified time instead. That said, here is my code:

module Kernel
alias normal_sleep sleep
def sleep(seconds)
normal_sleep(seconds) and return if seconds >= 0
priorities = {}
(Thread.list - [Thread.current]).each do |thread|
priorities[thread] = thread.priority
thread.priority = Thread.current.priority-1
end
Thread.new do
normal_sleep(-seconds)
priorities.each do |thread, priority|
thread.priority = priority
end
end
end
end

This is difficult to test cleanly since positive sleeping within the
current thread gives the de-prioritized threads a chance to run for a
short time (though I do see that as appropriate behavior… a thread
that is negative sleeping should still be able to positive sleep for
a short time). It is testable if you are willing to read extremely
long outputs or are willing to put up with using some long, empty
loops to minimize output.

  • Jake McArthur

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs