[QUIZ] Negative Sleep (#87)

[Ruby Quiz]

The three rules of Ruby Quiz:

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 Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk 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).

 

[Morton Goldberg]

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 Quiz. 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 Goldberg
#
# 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 = {
'@ ' => ' @',
'@.' => ' +',
'+ ' => '.@',
'+.' => '.+'
}

# Transition table for crate-pushing moves.
PUSH_TABLE = {
'@o ' => ' @o',
'@o.' => ' @*',
'@* ' => ' +o',
'@*.' => ' +*',
'+o ' => '.@o',
'+o.' => '.@*',
'+* ' => '.+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(r)}
@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)
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.newbeep)

# 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:OWN] = :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
catchgame_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
throwgame_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
throwgame_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 ---------------------------

 

[James Edward Gray II]

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 Quiz. It was from that book that I learned
about the Sokoban quiz.

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

James Edward Gray II

 

[Pierre Barbier de Reuille]

--------------090203040309040801070102
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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

--------------090203040309040801070102
Content-Type: text/plain;
name="sleep1.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="sleep1.rb"


class Sleep

attr_reader :time

def initialize time
@time = time
end

def <<(comp)
if Sleep === comp
@time += comp.time
self
else
Comp.new(time) << comp
end
end

end

class Comp

Op = Struct.new :time, p

attr_reader ps

def initialize(time = 0, &block)
@ops = []
@ops << Op.new(time, block) if block
@time = time
end

def <<(comp)
case comp
when Sleep
t = comp.time
@time += t
when Comp
@ops.concat comp.ops.map { |o| Op.new(o.time+@time, o.op) }
when Proc
@ops << Op.new(@time, comp)
end
self
end

def run
h = Hash.new { |h,k| h[k] = [] }
@ops.each do |c|
h[ c.time ] << c.op
end
order = h.keys.sort
time = order[0]
ref_time = time
order.each do |t|
sleep(t-time)
h[t].each { |b| b.call(t) }
time = t
end
end

end


--------------090203040309040801070102
Content-Type: text/plain;
name="sleep3.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="sleep3.rb"


class Sleep

attr_reader :time

def initialize time
@time = time
end

def <<(comp)
if Sleep === comp
@time += comp.time
self
else
Comp.new(time) << comp
end
end

end

class Comp

attr_reader ps

def initialize(time = 0, &block)
@ops = Hash.new { |h,k| h[k] = [] }
@ops[time] << block if block
@time = time
end

def <<(comp)
case comp
when Sleep
@time += comp.time
when Comp
comp.ops.each { |t,bs| @ops[t+@time].concat bs }
when Proc
@ops[@time] << comp
end
self
end

def run
ref_time = @ops.keys.min
ts = @ops.map do |t,bs|
Thread.new(bs) do |bs|
sleep(t-ref_time)
bs.each { |b| b.call(t) }
end
end
ts.each { |t| t.join }
end

end


--------------090203040309040801070102
Content-Type: text/plain;
name="sleep4.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="sleep4.rb"


class Sleep

attr_reader :time

def initialize time
@time = time
end

def <<(comp)
if Sleep === comp
@time += comp.time
self
else
Comp.new(time) << comp
end
end

end

class Comp

attr_reader ps

def initialize(time = 0, &block)
@ops = Hash.new { |h,k| h[k] = [] }
@ops[time] << block if block
@time = time
end

def <<(comp)
case comp
when Sleep
@time += comp.time
when Comp
comp.ops.each { |t,bs| @ops[t+@time].concat bs }
when Proc
@ops[@time] << comp
end
self
end

def run
ref_time = @ops.keys.min
ts = @ops.map do |t,bs|
bs.map do |b|
Thread.new(b) do |b|
sleep(t-ref_time)
b.call t
end
end
end
ts.flatten.each { |t| t.join }
end

end


--------------090203040309040801070102
Content-Type: text/plain;
name="test_sleep.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="test_sleep.rb"

require "sleep1"

puts "Test 1"

c = Comp.new { |t| sleep 1; puts "#{t} :: Foo here" } <<
Sleep.new(-1) <<
Comp.new { |t| puts "#{t} :: Bar there" } <<
Sleep.new(1) <<
Comp.new { |t| puts "#{t} :: Well ..." } <<
Comp.new { |t| puts "#{t} :: Why not" } <<
Sleep.new(-2) <<
Comp.new { |t| puts "#{t} :: Just another test" } <<
Sleep.new(2.5) <<
Comp.new { |t| puts "#{t} :: A last one ?" }
c.run

puts "Test 2"

c = Comp.new { |t| sleep 1; puts "#{t} :: Foo here" } <<
Sleep.new(-1) <<
Comp.new { |t| puts "#{t} :: Bar there" } <<
Sleep.new(2) <<
Comp.new { |t| puts "#{t} :: Well ..." } <<
Comp.new { |t| puts "#{t} :: Why not" } <<
Sleep.new(-3) <<
Comp.new { |t| puts "#{t} :: Just another test" }
c.run

puts "Test 3"

c = Comp.new(10) { |t| sleep 1; puts "#{t} :: Foo here" } <<
Sleep.new(-1) <<
lambda { |t| puts "#{t} :: Bar there" } <<
( Sleep.new(2) <<
Comp.new { |t| puts "#{t} :: Well ..." } <<
Comp.new { |t| puts "#{t} :: Why not" } <<
Sleep.new(-3) <<
Comp.new { |t| puts "#{t} :: Just another test" } ) <<
Sleep.new(1.5) <<
Comp.new { |t| puts "#{t} :: A last one ?" }
c.run


--------------090203040309040801070102--

 

[Dingsi]

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

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

 

[Mitchell Koch]

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

 

[Hal Fulton]

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 Quiz I've ever seen.

I like it a lot.


Hal

 

[Mike Nelson]

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.

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.

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

 

[Boris Prinz]

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

 

[Pit Capitain]

(...)
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 Gray II]

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:

But now we all want to see the code so we are curios why you didn't
submit it...

James Edward Gray II

 

[Pit Capitain]

But now we all want to see the code so we are curios why you didn't
submit it...

Yeah, I think I shouldn't have posted it, but I couldn't resist to make
you curious ;-)

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

 

[Adam Shelly]

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 Shelly]

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

 

[James Edward Gray II]

I just checked rubyquiz.com for some submissions and realized that
sending
my submission as tar.bz2 was, errr, not the best idea.
Maybe it would be a good idea to add a warning about it somewhere
or did I
overlook it?

The mailing list link requires a little work to extract it from,
yes. (I was to do that as a quiz someday.) However, I'm pretty
diligent. I have your code and it will be uploaded with the summary
on Thursday. No worries.

James Edward Gray II