Instantly share code, notes, and snippets.

# chadbrewbaker/queue_prod.rb Last active Dec 21, 2015

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