algorithm - C++ lambda function in priority_queue with capture by reference -


i solving algorithm problem - "find k-th ugly number", below problem statement , implementation.

write program find n-th ugly number. ugly numbers positive numbers prime factors include 2, 3, 5.  example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 sequence of first 10 ugly numbers.  vector<int> tmp(1,1); vector<int> primes({2,3,5}); vector<int> indices(3, 0); // lambda function pass in variables captured reference priority_queue<int, vector<int>, function<bool(const int&, const int&)>> pq([&](const int& a, const int& b){     return primes[a] * tmp[indices[a]] > primes[b] * tmp[indices[b]]; }); pq.push(0); pq.push(1); pq.push(2); while(tmp.size() <= 3) { // find first 3 ugly number     int primeindex = pq.top();     pq.pop();     int nextval = primes[primeindex] * tmp[indices[primeindex]];     pq.push(primeindex + 1);     indices[primeindex]++;      while(!pq.empty() && primes[pq.top()] & tmp[indices[pq.top()]]) {         primeindex = pq.top();         pq.pop();         pq.push(primeindex + 1);         indices[primeindex]++;     }     cout << nextval << endl;     tmp.push_back(nextval); } return 0;

the usage of priority_queue optimization solution. priority_queue finds "next ugly" number in o(logn) time. priority_queue uses index of primes[] elements. uses lambda function comparator , captures outside variables by reference. tested code output first 3 ugly numbers (should 2, 3, 4), code gave me "2, 6, 0". think there wrong lambda function in priority_queue, not find out why. give me hint on resolving bug? thank much.

the immediate problem code accessing tmp vector out of bounds. use elements of indices indices tmp, , increment elements of indices in multiple places within iteration of outer while loop (once before inner while loop, , potentially 1 or more times within inner while loop), , increase size of tmp @ end of iteration of outer while loop. in meantime, in condition of inner while loop, index tmp indices may have increased (potentially multiple times) before increasing size of tmp.


Comments

Post a Comment

Popular posts from this blog

python Tkinter Capturing keyboard events save as one single string -

is possible store keyboard events 1 string? code below stores 1 char , prints it. card reader or bar code reader, contains collection of character/ string not 1 character @ time. goal save char pressed text variable. from tkinter import * root = tk() def key(event): text= event.char text+= event.char print ("pressed", text) def callback(event): frame.focus_set() print ("clicked at", event.x, event.y) frame = frame(root, width=100, height=100) frame.bind("<key>", key) frame.bind("<button-1>", callback) frame.pack() root.mainloop() currently, creating text variable , everytime key() function gets called, , text stores last character typed. you can define text module level variable , , use module level text inside key function - text = '' def key(event): global text text+= event.char print("pressed", text)
Read more

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m
Read more

javascript - Z-index in d3.js -

i have map , when hover effect on region of map below yellow line , circle, last ones disappear. how can solve problem? http://jsfiddle.net/ot21n9qx/ var arc = g.append("path") .style("fill", "none") .style("stroke", "yellow") .style("stroke-width", 2) .attr("d", "m" + pathorigin[0] + "," + pathorigin[1] + " q" + svgpoint[0] + "," + pathorigin[1] + " " + svgpoint[0] + "," + svgpoint[1]); var circlesize = d3.scale.linear() .domain([0, 0.5, 1]) .range([4, 10, 4]); svg not have z order draws objects in order created. need create path , circle after create highlight regions. here forked fiddle: http://jsfiddle.net/o00fzgaf/1/
Read more