Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Demonstration of how to keep the product of a queue over a semigroup in amortized O(1) time
#Demonstration of how to keep the product of a queue over a semigroup in amortized O(1) time
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
inbox = []
inprod =[]
outbox = []
outprod = []
def enqueue_prod(inbox, inprod, elt)
inbox.push(elt)
if (inprod.size > 0)
inprod.push(inprod.last.to_s + "x"+elt.to_s)
else
inprod.push(elt.to_s)
end
end
def dequeue_prod(inbox, outbox, inprod, outprod)
if (outbox.size <1)
while inbox.size >0
elt = inbox.pop
inprod.pop
outbox.push(elt)
if (outprod.size >0)
outprod.push(elt.to_s + "x" + outprod.last.to_s)
else
outprod.push(elt.to_s)
end
end
end
outbox.pop
outprod.pop
end
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
enqueue_prod(inbox, inprod, arr.shift)
while (arr.size > 0)
puts "\ninbox " + inbox.inspect
puts "outbox " + outbox.inspect
puts "inbox_product " + inprod.inspect
puts "outbox_product " + outprod.inspect
dequeue_prod(inbox, outbox, inprod, outprod)
enqueue_prod(inbox, inprod, arr.shift)
total_prod =""
if (outprod.last != nil)
total_prod = total_prod + outprod.last
end
if (inprod.last != nil)
if(total_prod.length >0)
total_prod = total_prod + "x"
end
total_prod = total_prod + inprod.last
end
puts "Queue product is "+ total_prod
end
#Expected output
#inbox [1, 2, 3, 4, 5]
#outbox []
#inbox_product ["1", "1x2", "1x2x3", "1x2x3x4", "1x2x3x4x5"]
#outbox_product []
#Queue product is 2x3x4x5x6
#
#inbox [6]
#outbox [5, 4, 3, 2]
#inbox_product ["6"]
#outbox_product ["5", "4x5", "3x4x5", "2x3x4x5"]
#Queue product is 3x4x5x6x7
#
#inbox [6, 7]
#outbox [5, 4, 3]
#inbox_product ["6", "6x7"]
#outbox_product ["5", "4x5", "3x4x5"]
#Queue product is 4x5x6x7x8
#
#inbox [6, 7, 8]
#outbox [5, 4]
#inbox_product ["6", "6x7", "6x7x8"]
#outbox_product ["5", "4x5"]
#Queue product is 5x6x7x8x9
#
#inbox [6, 7, 8, 9]
#outbox [5]
#inbox_product ["6", "6x7", "6x7x8", "6x7x8x9"]
#outbox_product ["5"]
#Queue product is 6x7x8x9x10
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.