Search Results

Search found 96 results on 4 pages for 'greedy'.

Page 1/4 | 1 2 3 4  | Next Page >

• How to non-greedy multiple lookbehind matches

  - by ArtK

  Source: <prefix><content1><suffix1><prefix><content2><suffix2> Engine: PCRE RegEx1: (?<=<prefix>)(.*)(?=<suffix1>) RegEx2: (?<=<prefix>)(.*)(?=<suffix2>) Result1: <content1> Result2: <content1><suffix1><prefix><content2> The desired result for RegEx2 is just <content2> but it is obviously greedy. How do I make RegEx2 non-greedy and use only the last matching lookbehind? [I hope I have translated this correctly from the NoteTab syntax. I don't do much RegEx coding. The <prefix>, <content> & <suffix> terms are just meant to represent arbitrary strings. Only the "<" in the "?<=" lookbehind command is significant.] I suspect it is something simple but after too many hours of searching I'm giving up on solving it myself. Thanks for the help Art

  Read the article

• Sed non greedy curly braces match

  - by Cesar

  I have a string in a file a.txt {moslate}alho{/moslate}otra{moslate}a{/moslate} a need to get the string otra using sed. With this regex sed 's|{moslate}.*{/moslate}||g' a.txt a get no output at all but when i add a ? to the regex s|{moslate}.*?{/moslate}||g a.txt (I've read somewhere that it makes the regex non-greedy) i get no match at all, i mean a get the following output {moslate}alho{/moslate}otra{moslate}a{/moslate} How can i get the required output using sed?

  Read the article

• Voxel Face Crawling (Mesh simplification, possibly using greedy)

  - by Tim Winter

  This is in regards to a Minecraft-like terrain engine. I store blocks in chunks (16x256x16 blocks in a chunk). When I generate a chunk, I use multiple procedural techniques to set the terrain and to place objects. While generating, I keep one 1D array for the full chunk (solid or not) and a separate 1D array of solid blocks. After generation, I iterate through the solid blocks checking their neighbors so I only generate block faces that don't have solid neighbors. I store which faces to generate in their own list (that's 6 lists, one per possible face). When rendering a chunk, I render all lists in the camera's current chunk and only the lists facing the camera in all other chunks. Using a 2D atlas with this little shader trick Andrew Russell suggested, I want to merge similar faces together completely. That is, if they are in the same list (same normal), are adjacent to each other, have the same light level, etc. My assumption would be to have each of the 6 lists sorted by the axis they rest on, then by the other two axes (the list for the top of a block would be sorted by it's Y value, then X, then Z). With this alone, I could quite easily merge strips of faces, but I'm looking to merge more than just strips together when possible. I've read up on this greedy meshing algorithm, but I am having a lot of trouble understanding it. To even use it, I would think I'd need to perform a type of flood-fill per sorted list to get the groups of merge-able faces. Then, per group, perform the greedy algorithm. It all sounds awfully expensive if I would ever want dynamic terrain/lighting after initial generation. So, my question: To perform merging of faces as described (ignoring whether it's a bad idea for dynamic terrain/lighting), is there perhaps an algorithm that is simpler to implement? I would also quite happily accept an answer that walks me through the greedy algorithm in a much simpler way (a link or explanation). I don't mind a slight performance decrease if it's easier to implement or even if it's only a little better than just doing strips. I worry that most algorithms focus on triangles rather than quads and using a 2D atlas the way I am, I don't know that I could implement something triangle based with my current skills. PS: I already frustum cull per chunk and as described, I also cull faces between solid blocks. I don't occlusion cull yet and may never.

  Read the article

• How do I enable greedy MigrationHeuristic in Karmic?

  - by Matthew

  My laptop performs very poorly for 2d graphics. For example, Docky's zoom effect and compiz effects are very choppy. In Jaunty, I was able to fix this by adding the following line under the "Device" section in my xorg.conf: Option "MigrationHeuristic" "greedy" In Karmic, there is no xorg.conf by default, so I copied my old one (from Jaunty). However, everything is still slow. Here is my xorg.conf: Section "Device" Identifier "Configured Video Device" Option "MigrationHeuristic" "greedy" EndSection Section "Monitor" Identifier "Configured Monitor" EndSection Section "Screen" Identifier "Default Screen" Monitor "Configured Monitor" Device "Configured Video Device" EndSection From googling about, it sounds like "MigrationHeuristic" is only an option for the "EXA" mode, while Karmic has switched the intel driver to "UXA". So I tried adding this line under the "Device" section: Option "AccelMethod" "exa" But this didn't help.

  Read the article

• non greedy grep command on ubuntu?

  - by ChrisRamakers

  Hi all, I'm building a script which filters out all our translatables from our template system. the problem i'm facing is the occasion where 2 translatables are on one line. These are 2 example lines from a template file which both hold one or more translatables <img src="/captcha/generate.jpg" alt="[#Captcha#]" /> <span>[#Velden met een * zijn verplicht in te vullen#]</span> <button type="submit" name="frm_submit" class="right">[#Verzend#] And when i set loose the following regexp egrep "\[#(.*)#\]" . -Rohis I get this output [#Captcha#]" [#Velden met een * zijn verplicht in te vullen#]</span> <button type="submit" name="frm_submit" class="right">[#Verzend#] While the desired output is [#Captcha#] [#Velden met een * zijn verplicht in te vullen#] [#Verzend#]

  Read the article

• Perl: Greedy nature refuses to work

  - by faezshingeri

  I am trying to replace a string with another string, but the greedy nature doesn't seem to be working for me. Below is my code where "PERFORM GET-APLCY" is identified and replaced properly, but string "PERFORM GET-APLCY-SOI-CVG-WVR" and many other such strings are being replaced by the the replacement string for "PERFORM GET-APLCY". s/PERFORM $func[$i]\.?/# PERFORM $func[$i]\.\n $hash{$func[$i]}/g; where the full stop is optional during string match and replacement. Please help me understand what the issue could be. Thanks in advance, Faez

  Read the article

• Problem with logicalOR ( regex ) not greedy

  - by Marin Doric

  This is the part of a string "21xy5". I want to insert " * " surrounded with whitespace between: digit and letter, letter and digit, letter and letter. I use this regex pattern "\d[a-z]|[a-z]\d|[a-z][a-z]" to find indexs where I gona insert string " * ". Problem is that when regex OR(|) in string 21xy5 trays to match 21-x|x-y|y-5, when first condition 21-x success, second x-y is not checked, and third success. So I have 21 * xy * 5 instead 21 * x * y * 5. If input string is like this xy21, then x-y success and then I have x * y21. Problem is that logical OR is not greedy. Regex reg = new Regex(@"\d[a-z]|[a-z]\d|[a-z][a-z]" ); MatchCollection matchC; matchC = reg.Matches(input); int ii = 1; foreach (Match element in matchC) { input = input.Insert(element.Index + ii, " * "); ii += 3; } return input;

  Read the article

• Regex expression is too greedy

  - by alastairs

  I'm writing a regular expression to match data from the IMDb soundtracks data file. My regexes are mostly working, although they are in places slurping too much text into my named groups. Take the following regex for example: "^ Performed by '?(?<performer>.*)('? \(qv\))?$" The performer group includes the string ' (qv) as well as the performer's name. Unfortunately, because the records are not consistently formatted, some performers' names are surrounded by single quotation marks whilst others are not. This means they are optional as far as the regex is concerned. I've tried marking the last group as a greedy group using the ?> group specifier, but this appeared to have no effect on the results. I can improve the results by changing the performer group to match a small range of characters, but this reduces my chances of parsing the name out correctly. Furthermore, if I were to just exclude the apostrophe character, I would then be unable to parse, e.g., band names containing apostrophes, such as Elia's Lonely Friends Band who performed Run For Your Life featured in Resident Evil: Apocalypse.

  Read the article

• Bubble Breaker Game Solver better than greedy?

  - by Gregory

  For a mental exercise I decided to try and solve the bubble breaker game found on many cell phones as well as an example here:Bubble Break Game The random (N,M,C) board consists N rows x M columns with C colors The goal is to get the highest score by picking the sequence of bubble groups that ultimately leads to the highest score A bubble group is 2 or more bubbles of the same color that are adjacent to each other in either x or y direction. Diagonals do not count When a group is picked, the bubbles disappear, any holes are filled with bubbles from above first, ie shift down, then any holes are filled by shifting right A bubble group score = n * (n - 1) where n is the number of bubbles in the bubble group The first algorithm is a simple exhaustive recursive algorithm which explores going through the board row by row and column by column picking bubble groups. Once the bubble group is picked, we create a new board and try to solve that board, recursively descending down Some of the ideas I am using include normalized memoization. Once a board is solved we store the board and the best score in a memoization table. I create a prototype in python which shows a (2,15,5) board takes 8859 boards to solve in about 3 seconds. A (3,15,5) board takes 12,384,726 boards in 50 minutes on a server. The solver rate is ~3k-4k boards/sec and gradually decreases as the memoization search takes longer. Memoization table grows to 5,692,482 boards, and hits 6,713,566 times. What other approaches could yield high scores besides the exhaustive search? I don't seen any obvious way to divide and conquer. But trending towards larger and larger bubbles groups seems to be one approach Thanks to David Locke for posting the paper link which talks above a window solver which uses a constant-depth lookahead heuristic.

  Read the article

• Non greedy grep

  - by syker

  I want to grep the shortest match and the pattern should be something like: <car ... model=BMW ...> ... ... ... </car> ... means any character and the input is multiple lines.

  Read the article

• how to make Regular expression into non-greedy ?

  - by Rueta

  Hi everyone! I have made a Work with JQ. My Work is a string width a special character block begin and end of string. I want take the text in that special characters, i used regular expression for find in string, but how to make JQ find multi result when have two special character or more. My html here; <div id="container"> <div id="textcontainer"> Cu?c chi?n pháp lý gi?a [|co th?|nghi?m|] th? tru?ng [|test2|dây là test l?n 2|] ch?ng khoán [|M?|day la nuoc my|] và ngân hàng d?u tu quy?n l?c nh?t Ph? Wall m?i ch? b?t d?u. </div> </div> and my JQ $(document).ready(function() { var takedata = $("#textcontainer").text(); var test = 'abcd adddb'; var filterdata = takedata.match(/(\[.+\])/); alert(filterdata); //end write js }); my result is: [|co th?|nghi?m|] th? tru?ng [|test2|dây là test l?n 2|] ch?ng khoán [|M?|day la nuoc my|] . but this is'nt the result i want :(. How to get [text] for times 1 and [demo] for times 2 ?. pls help me !. thankyou :)

  Read the article

• RewriteRule being greedy

  - by lardlad

  I have been looking for an answer for a few hours now, so sorry if this was asked a ton of times, I missed it. I basically want to make a rewrite to ignore the first directory. That first dir in the path will be different so I thought I could use a regex. But my regex is matching all the way to the file name: RewriteRule ^([a-z]+)?/(.+)$ $2 [L] this works if I am one level deep: http://test.domain.com/one/index.php I get the actual index page of the root. Which is what I want. but if I were to go deeper: http://test.domain.com/one/two/index.php I get a message saying /index.php was not found. So it seems my regex is not stopping after the last [a-z]. I appreciate any help. This is Apache2 if that matters at all.

  Read the article

• Regex not being greedy enough

  - by Chad

  I've got the following regex that was working perfectly until a new situation arose ^.*[?&]U(?:RL)?=(?<URL>.*)$ Basically, it's used against URLs, to grab EVERYTHING after the U=, or URL= and return it in the URL match So, for the following http://localhost?a=b&u=http://otherhost?foo=bar URL = http://otherhost?foo=bar Unfortunately an odd case came up http://localhost?a=b&u=http://otherhost?foo=bar&url=http://someotherhost Ideally, I want URL to be "http://otherhost?foo=bar&url=http://someotherhost", instead, it is just "http://someotherhost"

  Read the article

• Point covering problem

  - by Sean

  I recently had this problem on a test: given a set of points m (all on the x-axis) and a set n of lines with endpoints [l, r] (again on the x-axis), find the minimum subset of n such that all points are covered by a line. Prove that your solution always finds the minimum subset. The algorithm I wrote for it was something to the effect of: (say lines are stored as arrays with the left endpoint in position 0 and the right in position 1) algorithm coverPoints(set[] m, set[][] n): chosenLines = [] while m is not empty: minX = min(m) bestLine = n[0] for i=1 to length of n: if n[i][0] <= m and n[i][1] > bestLine[1] then bestLine = n[i] add bestLine to chosenLines for i=0 to length of m: if m <= bestLine[1] then delete m[i] from m return chosenLines I'm just not sure if this always finds the minimum solution. It's a simple greedy algorithm so my gut tells me it won't, but one of my friends who is much better than me at this says that for this problem a greedy algorithm like this always finds the minimal solution. For proving mine always finds the minimal solution I did a very hand wavy proof by contradiction where I made an assumption that probably isn't true at all. I forget exactly what I did. If this isn't a minimal solution, is there a way to do it in less than something like O(n!) time? Thanks

  Read the article

• Scala: Can I nudge a combinator parser to be locally greedy?

  - by eed3si9n

  Suppose I have an ambiguous language expressed in combinator parser. Is there a way to make certain expressions locally greedy? Here's an example of what I mean. import scala.util.parsing.combinator._ object Example extends JavaTokenParsers { def obj: Parser[Any] = (shortchain | longchain) ~ anyrep def longchain: Parser[Any] = zero~zero~one~one def shortchain: Parser[Any] = zero~zero def anyrep: Parser[Any] = rep(any) def any: Parser[Any] = zero | one def zero: Parser[Any] = "0" def one: Parser[Any] = "1" def main(args: Array[String]) { println(parseAll(obj, args(0) )) } } After compiling, I can run it as follows: $ scala Example 001111 [1.7] parsed: ((0~0)~List(1, 1, 1, 1)) I would like to somehow instruct the first part of obj to be locally greedy and match with longchain. If I switch the order around, it matches the longchain, but that's not because of the greediness. def obj: Parser[Any] = (longchain | shortchain) ~ anyrep

  Read the article

• Memory limiting solutions for greedy applications that can crash OS?

  - by Hooked

  I use my computer for scientific programming. It has a healthy 8GB of RAM and 12GB of swap space. Often, as my problems have gotten larger, I exceed all of the available RAM. Rather than crashing (which would be preferred), it seems Ubuntu starts loading everything into swap, including Unity and any open terminals. If I don't catch a run-away program in time, there is nothing I can do but wait - it takes 4-5 minutes to switch to a command prompt eg. Ctrl-Alt-F2 where I can kill the offending process. Since my own stupidity is out of scope of this forum, how can I prevent Ubuntu from crashing via thrashing when I use up all of the available memory from a single offending program? At-home experiment*! Open a terminal, launch python and if you have numpy installed try this: >>> import numpy >>> [numpy.zeros((10**4, 10**4)) for _ in xrange(50)] * Warning: may have adverse effects, monitor the process via iotop or top to kill it in time. If not, I'll see you after your reboot.

  Read the article

• Searching Algorithms implemented in C#

  A* Seach , Greedy Search , BSF, DFS Search Algorithms

  Read the article

• Asp.net MVC Route class that supports catch-all parameter anywhere in the URL

  - by Robert Koritnik

  the more I think about it the more I believe it's possible to write a custom route that would consume these URL definitions: {var1}/{var2}/{var3} Const/{var1}/{var2} Const1/{var1}/Const2/{var2} {var1}/{var2}/Const as well as having at most one greedy parameter on any position within any of the upper URLs like {*var1}/{var2}/{var3} {var1}/{*var2}/{var3} {var1}/{var2}/{*var3} There is one important constraint. Routes with greedy segment can't have any optional parts. All of them are mandatory. Example This is an exemplary request http://localhost/Show/Topic/SubTopic/SubSubTopic/123/This-is-an-example This is URL route definition {action}/{*topicTree}/{id}/{title} Algorithm Parsing request route inside GetRouteData() should work like this: Split request into segments: Show Topic SubTopic SubSubTopic 123 This-is-an-example Process route URL definition starting from the left and assigning single segment values to parameters (or matching request segment values to static route constant segments). When route segment is defined as greedy, reverse parsing and go to the last segment. Parse route segments one by one backwards (assigning them request values) until you get to the greedy catch-all one again. When you reach the greedy one again, join all remaining request segments (in original order) and assign them to the greedy catch-all route parameter. Questions As far as I can think of this, it could work. But I would like to know: Has anyone already written this so I don't have to (because there are other aspects to parsing as well that I didn't mention (constraints, defaults etc.) Do you see any flaws in this algorithm, because I'm going to have to write it myself if noone has done it so far. I haven't thought about GetVirtuaPath() method at all.

  Read the article

• algorithm for project euler problem no 18

  - by Valentino Ru

  Problem number 18 from Project Euler's site is as follows: By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3 That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from top to bottom of the triangle below: 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o) The formulation of this problems does not make clear if the "Traversor" is greedy, meaning that he always choosed the child with be higher value the maximum of every single walkthrough is asked The NOTE says, that it is possible to solve this problem by trying every route. This means to me, that is is also possible without! This leads to my actual question: Assumed that not the greedy one is the max, is there any algorithm that finds the max walkthrough value without trying every route and that doesn't act like the greedy algorithm? I implemented an algorithm in Java, putting the values first in a node structure, then applying the greedy algorithm. The result, however, is cosidered as wrong by Project Euler. sum = 0; void findWay(Node node){ sum += node.value; if(node.nodeLeft != null && node.nodeRight != null){ if(node.nodeLeft.value > node.nodeRight.value){ findWay(node.nodeLeft); }else{ findWay(node.nodeRight); } } }

  Read the article

• How to explain that writing universally cross-platform C++ code and shipping products for all OSes is not that easy?

  - by sharptooth

  Our company ships a range of desktop products for Windows and lots of Linux users complain on forums that we should have been written versions of our products for Linux years ago and the reason why we don't do that is we're a greedy corporation all our technical specialists are underqualified idiots Our average product is something like 3 million lines of C++ code. My and my colleagues analysis is the following: writing cross-platform C++ code is not that easy preparing a lot of distribution packages and maintaining them for all widespread versions of Linux takes time our estimate is that Linux market is something like 5-15% of all users and those users will likely not want to pay for our effort when this is brought up the response is again that we're greedy underqualified idiots and that when everything is done right all this is easy and painless. How reasonable are our evaluations of the fact that writing cross-platform code and maintaining numerous ditribution packages takes lots of effort? Where can we find some easy yet detailed analysis with real life stories that show beyond the shadow of a doubt what amount of effort exactly it takes?

  Read the article

• PCRE (recursive) pattern that matches a string containing a correctly parenthesized substring. Why d

  - by Anton N. Petrov

  Well, there are other ways (hmmm... or rather working ways) to do it, but the question is why does this one fail? / \A # start of the string ( # group 1 (?: # group 2 [^()]* # something other than parentheses (greedy) | # or \( (?1) \) # parenthesized group 1 ) # -group 2 + # at least once (greedy) ) # -group 1 \Z # end of the string /x Fails to match a string with nested parentheses: "(())"

  Read the article

• Multiline Replacement With Visual Studio

  - by Alois Kraus

  I had to remove some file headers in a bigger project which were all of the form #region File Header /*[ Compilation unit ----------------------------------------------------------       Name            : Class1.cs       Language        : C#     Creation Date   :      Description     : -----------------------------------------------------------------------------*/ /*] END */ #endregion I know that would be a cool thing to write a simple C# program use a recursive file search, read all lines skip the first n lines and write the files back to disc. But I wanted to test things first before I ruin my source files with one little typo. There comes the Visual Studio Search and Replace in Files dialog into the game. I can test my regular expression to do a multiline match with the Find button before actually breaking anything. And if something goes wrong I have the Undo button.   There is a nice blog post from Paulo Morgado online who deals with Multiline Regular expressions. The Visual Studio Regular expressions are non standard so you have to adapt your usual Regex know how to the other patterns. The pattern I cam finally up with is \#region File Header:b*(.*\n)@\#endregion The Regular expression can be read as \#region File Header Match “#region File Header” \# Escapes the # character since it is a quantifier. :b* After this none or more spaces or tabs can follow (:b stands for space or tab) (.*\n)@ Match anything across lines in a non greedy way (the @ character makes it non greedy) to prevent matching too much until the #endregion somewhere in our source file. \#endregion Match everything until “#endregion” is found I had always knew that Visual Studio can do it but I never bothered to learn the non standard Regex syntax. This is powerful and it is inside Visual Studio since 2005!

  Read the article

• Converting a bounded knapsack problem to 0/1 knapsack problem

  - by Ants

  I ran across a problem where goal was to use dynamic programming (instead of other approaches). There is a distance to be spanned, and a set of cables of different lengths. What is the minimum number of cables needed to span the distance exactly? To me this looked like a knapsack problem, but since there could be multiples of a particular length, it was a bounded knapsack problem, rather than a 0/1 knapsack problem. (Treat the value of each item to be its weight.) Taking the naive approach (and not caring about the expansion of the search space), the method I used to convert the bounded knapsack problem into a 0/1 knapsack problem, was simply break up the multiples into singles and apply the well-known dynamic programming algorithm. Unfortunately, this leads to sub-optimal results. For example, given cables: 1 x 10ft, 1 x 7ft, 1 x 6ft, 5 x 3ft, 6 x 2ft, 7 x 1ft If the target span is 13ft, the DP algorithm picks 7+6 to span the distance. A greedy algorithm would have picked 10+3, but it's a tie for minimum number of cables. The problem arises, when trying to span 15ft. The DP algorithm ended up picking 6+3+3+3 to get 4 cables, while the greedy algorithm correctly picks 10+3+2 for only 3 cables. Anyway, doing some light scanning of converting bounded to 0/1, it seems like the well-known approach to convert multiple items to { p, 2p, 4p ... }. My question is how does this conversion work if p+2p+4p does not add up to the number of multiple items. For example: I have 5 3ft cables. I can't very well add { 3, 2x3, 4x3 } because 3+2x3+4x3 5x3. Should I add { 3, 4x3 } instead? [I'm currently trying to grok the "Oregon Trail Knapsack Problem" paper, but it currently looks like the approach used there is not dynamic programming.]

  Read the article

• computing "node closure" of graph with removal

  - by Fakrudeen

  Given a directed graph, the goal is to combine the node with the nodes it is pointing to and come up with minimum number of these [lets give the name] super nodes. The catch is once you combine the nodes you can't use those nodes again. [first node as well as all the combined nodes - that is all the members of one super node] The greedy approach would be to pick the node with maximum out degree and combine that node with nodes it is pointing to and remove all of them. Do this every time with the nodes which are not removed yet from graph. The greedy is O(V), but this won't necessarily output minimum number super nodes. So what is the best algorithm to do this?

  Read the article

• PHP: friend classes and ungreedy caller function/class

  - by avetis.kazarian

  Is there any way to get the caller function with something else than debug_backtrace()? I'm looking for a less greedy way to simulate scopes like friend or internal. Let's say I have a class A and a class B. Until now, I've been using debug_backtrace(), which is too greedy (IMHO). I thought of something like this: <?php class A { public function __construct(B $callerObj) {} } class B { public function someMethod() { $obj = new A($this); } } ?> It might be OK if you want to limit it to one specific class, but let's say I have 300 classes, and I want to limit it to 25 of them? One way could be using an interface to aggregate: public function __construct(CallerInterface $callerObj) But it's still an ugly code. Moreover, you can't use that trick with static classes. Have any better idea?

  Read the article

1 2 3 4  | Next Page >