User talk:Ledrug

From Rosetta Code

Common Lisp Implementation

If as you say you want to reopen this discussion then please add somthing to it here. If you have nothing to add then neither have I.

Levenshtein distance C code

I Just noticed that you posted a recursive C solution for Levenshtein distance. Could you maybe explain (here or in/near the example) what the variables mean in that solution? I tried to come up with a recursive solution in Java myself, but it didn't work out so well. If at all possible could you maybe just give some pseudocode for the recursive algorithm? --Mwn3d 20:25, 20 June 2011 (UTC)

The recursion function has 4 parameters: s, string 1; ls: length of s; t: string 2; lt length of t. Basically, <lang>function levenschtein(s, t)
   if length(s) = 0: return length(t)
   if length(t) = 0: return length(s)
   if s[0] = t[0]  : return levelschtein(s[1 .. end], t[1 .. end])
   len1 := levelschtein(s, t[1 .. end]) + 1
   len2 := levelschtein(s[1 .. end], t) + 1
   len3 := levelschtein(s[1 .. end], t[1 .. end]) + 1
   return min(len1, len2, len3)

</lang>where s[0] meaning first char in string s; s[1 .. end] meaning s without first char. (heh this reads just like the C code. I suck at pseudo code.) --Ledrug 20:39, 20 June 2011 (UTC)

Oh duh. C strings. Forgot about passing around lengths separately. So this says if either string is empty, return the length of the other string (because you just insert or delete all of the other string). If the first chars are the same, nothing needs to happen so just ignore them. Otherwise try deleting one char (len1), inserting one char (len2), or essentially making the first chars the same (as len3 but count the move this time), and return the minimum distance from those. OK I think I got it. Thanks for that. It's really close to what I was thinking of when I tried to do it, but this makes much more sense. I'll try to translate it soon. --Mwn3d 20:50, 20 June 2011 (UTC)
Any chance you might add this to the tasks talk page? I'll be adding a (memoized) version of this in the Python section. Thanks. --Paddy3118 21:45, 20 June 2011 (UTC)
But the wikipedia solution is the memoized version, though? --Ledrug 22:26, 20 June 2011 (UTC)
Hi, there are no recursive calls here. --Paddy3118 05:15, 21 June 2011 (UTC)
Yeah I know, I meant if you memoize the results and convert recursion to iteration, they are exactly the same algorithm. I guess recursive version expresses the idea better, maybe. --Ledrug 05:18, 21 June 2011 (UTC)

Hough transform C code

Rather than adding {{incorrect}}, it's probably more appropriate to just fix the code. Also, while I definitely appreciate the expertise and perspective I've seen you bringing to many areas across the wiki, calling code out as a 'shame', particularly in the page body itself, is inappropriate. Since the code implements the task, it's technically correct. If you'd like to raise suggested fixes (without implementing them yourself), you should raise them in the talk pages, as you've been doing elsewhere. --Michael Mol 01:10, 23 June 2011 (UTC)

Point 3 was minor, the key issue was the black artifact at bottom and the processing order. Yes I shouldn't called it a shame, sorry. I was looking at coding it, but I need to simple down the lib requirement first. --Ledrug 01:14, 23 June 2011 (UTC)
That "shame code" wanted to be a as close as possible translation of the Tcl code, that could have been useful in comparing (languages), and if such a translation had bugs, it could have been fixed; any other non-technical word (and especially subjective one) can be left out or put elsewhere as a mean of starting a hopefully useful (teach and learn) discussion about interesting "facts", if there are any. For what is worth, I refrain from replacing working code just for my aesthetic beliefs and even for what I know or think could be "best practices" without considering carefully the reasons or trying to inherit as much as possible (by the code, or by the wiki, e.g. consider the PNM related tasks). --ShinTakezou 17:15, 21 May 2012 (UTC)
And the argument is even stronger when there are no "artifact" to be fixed, just taste. I don't even understand "self-commenting" like "good luck printing out your token stack as a table: there isn't one.". If there is something unclear in the task that you've noticed, write in the talk page. --ShinTakezou 17:21, 21 May 2012 (UTC)
If you have a better solution (or different idiomatic solution, or an explicit translation, though those don't tend to last very long in the face of interested parties), put it side-by-side next to the existing code. I see that the original C code was replaced. Don't get offended; if you like, add your vision of the code next to the current version and move on. Yes, I realize Ledrug didn't do this last June. He was also new to the site, and there's very little codified in terms of RC netiquette, and what uncodified netiquette exists is flexible to the needs of the circumstance. --Michael Mol 16:20, 22 May 2012 (UTC)


Not going to drop the boilerplate greeting; I need to update it, I think. However, I've seen you as one of a few particularly active new users in the last few months, you've been getting a feel for the wiki and its habits, and it's pretty cool. Keep it up! :) --Michael Mol 01:11, 23 June 2011 (UTC)

Thanks! --Ledrug
You ever going to get around to populating your user page, perhaps with {{mylang}}? :P --Michael Mol 02:54, 13 August 2011 (UTC)


Your ascii based deathstar solution is truly excellent. :-)

Last Fridays

Hi, your C code for "Last Fridays" is quite complicated. Maybe some explanations about the calculation done (or comments in the code) would be a good idea, don't you think? Blue Prawn 21:13, 9 November 2011 (UTC)

There are only 5 statements in the code, one of which deals with command line args, two others calculate leap years. I'm not sure, what kind of comments would be helpful and not redundant? --Ledrug 01:26, 10 November 2011 (UTC)
Where did this line come from?:

<lang c>w = y * 365 + (y - 1) / 4 - (y - 1) / 100 + (y - 1) / 400 + 6;</lang>

I understand that it is math and what multiplication is, but I don't know how it is relevant. --Mwn3d 01:43, 10 November 2011 (UTC)
That's the number of days between Jan 0th of year y and some unspecified past date. All we need is that that number modulo 7 gives day of week of Jan 0th, y AD. --Ledrug 02:09, 10 November 2011 (UTC)
Is "Jan 0th" just Dec 31 of the previous year? Where did the formula come from? --Mwn3d 02:21, 10 November 2011 (UTC)
it is a formula that takes leap years into account: a year has 365 days, except every 4 years (y-1)/4, when it has 366, so those need to be added. but, every 100 years is not a leap year (y-1)/100, so those need to be subtracted again, and then every 400 years is a leap year again so (y-1)/400 needs to be added back. it is pretty straightforward once analyzed. i don't know what the +6 at the end is for though.--eMBee 03:22, 10 November 2011 (UTC)
Jan 0th is the day before Jan 1st, it doesn't quite matter what that means, as long as, say, Jan 0th + 10 days = Jan 10th. The "+6" to the number of days is so that the number modulo 7 gives the day of week, it just so happens that it's 6. --Ledrug 05:05, 10 November 2011 (UTC)


Could you please post the output image for your solution. Thanks. (See talk, my error). --Dgamey 03:31, 15 November 2011 (UTC)

AutoHotkey image

I'm interested in how you got the AutoHotkey image on Yin_and_yang to upload to Rosetta Code; when I tried it wouldn't work. In fact, even now when I download the file from imgur and attempt to upload it, it still fails, showing the "supported file types" in red. Perhaps it's the browser? I use Google Chrome... This would really be a help; I've had problems with it in the past. While we're on the topic, would it be OK to upload the large image as well? (Second Image in the imgur link.) If it's too large, I could simply run the AHK script again with a smaller width and height parameter. --Crazyfirex 03:20, 19 November 2011 (UTC)

I don't really know why one can or cannot upload an image, but I did convert your blobs from indexed mode to grayscale before uploading, maybe that has something to do with it. I have replaced the image with your bigger verseion now (I had javascript disabled the first time I followed the link, so didn't see it there at all). If you think it's too big, set a size parameter on it like this: [[file:yin-yang-ahk.png|right|150px]]. --Ledrug 03:28, 19 November 2011 (UTC)
Well, it's smaller than both the PicoLisp and ALGOL's ASCII outputs, and it doesn't disrupt the code, so I don't think anyone will object to the size. What tool did you use to convert them? Maybe I can use it in the future. In any case, thanks for uploading it. --Crazyfirex 03:40, 19 November 2011 (UTC)
I used GIMP to convert it. Imagemagick might work, too (however, if it did, there would be no reason for this conversion since MediaWiki uses it internally to scale images). --Ledrug 03:49, 19 November 2011 (UTC)
Well here we go again... I solved with AutoHotkey, and the wiki won't let me upload a screenshot. Interestingly enough, I didn't make the image with AHK, but with Prt Scr + Paint. Would you be so kind as to upload this? ...I feel so needy
Done. Check the task page to see if you are ok with the format. --Ledrug 02:58, 10 December 2011 (UTC)
We still have a workaround for the image upload problem. It's weird but it seems to work. Also I think disabling Javascript in your browser makes it work. --Mwn3d 03:56, 10 December 2011 (UTC)
Beggars can't be choosers. It looks fine to me. (Also, I like the comment. If you think it looks trippy now, run the script and see it in fullscreen at native resolution. O.O) --Crazyfirex 04:29, 10 December 2011 (UTC)
I wouldn't know: I never had problem uploading bitmap images. You probably want to talk to Crazyfirex instead. --Ledrug 04:07, 10 December 2011 (UTC)
That's interesting. I'll try it on the next task. Thanks. --Crazyfirex 04:29, 10 December 2011 (UTC)
Turning off javascript works. Thank you very much! I tested it at Constrained_random_points_on_a_circle. --Crazyfirex 03:31, 11 December 2011 (UTC)

Zebra puzzle

Cudos for catching this! :) I remembered to fix the one thing but forgot about the other... Cheers. WillNess 06:41, 3 December 2011 (UTC)

Is there any documentation for the version of the code that is written and runs as PERL? "Cacher (talk) 03:54, 5 August 2014 (UTC)"

The setting up of the "property names and values" is straight forward, but the "constraints" section is a bit difficult to figure out. Confused by the required order of the constraints and what to do when the hint is stated as the separation of two houses.

Trying to set up the following variant of the puzzle:

Puzzle: Given the following, where does everybody live?

  1. There is one house between the person eating potatoes and the person eating pancakes.
  2. The fourth house is white.
  3. The German drinks water.
  4. The German lives directly to the right of the horses.
  5. The butterflies live directly next to the brown house.
  6. The person in house two eats eggs.
  7. The person in house one drinks icetea.
  8. The person smoking pipe lives directly to the right of the person eating pancakes.
  9. The person eating spaghetties lives directly to the right of the white house.
  10. The Swede does not live in house one.
  11. There are two houses between the house of the person drinking coffee and the black house on the right
  12. There are two houses between the Spanish and the Dunhill smoking person on the left
  13. The person smoking Chersterfields lives directly to the left of the person smoking Cubans.
  14. The person eating potatoes lives directly next to the blue house.
  15. The British lives directly to the left of the birds.
  16. There are two houses between the turtles and the person drinking milk on the right
  17. The first house is brown.
  18. The person smoking Cubans eats spaghetties.

Answer: Should be: Spanish (4), German (5), Swede (3), British (2), Greek (1)

Amazon links

The amazon links do carry commission for RC, but I agree they shouldn't be required for tasks unless necessary. Obviously, if the Amazon links harm the the site's utility to any of RC's class of visitors, they're inappropriate. Still, I'd like to see them available as additional resources references, where they're useful. --Michael Mol 03:57, 24 December 2011 (UTC)

I sort of expected that, that's why I left the Amazon link alone. For the specific task, the book authors' page has a link to Amazon, while it's hard to go from Amazon to that page. Most users interested in that task probably only need some context instead of the whole book, so a way to read a single chapter should be useful. --Ledrug 04:26, 24 December 2011 (UTC)

Lisp in the style of the C++ generator

Please leave this code alone until you can demonstrate an understanding of this problem. Your second attempt at this is an improvement over your first naive attempt, but still not as interesting as this. Maybe I shall seperate the Casting_out_nines from the Kaprecar part: <lang clisp>(let ((kk (* N N))) (do ((B Base (* B Base))) ()(let (( nr (/ (* N (- B N)) (- B 1)))) (if (< 0 nr) (let ((q (floor (- N nr)))) (if (= kk (+ nr (* q B)))</lang>

Glitch in "Cut a rectangle" / CommonLisp

In Cut_a_rectangle#Common_Lisp the fourth line reading <lang lisp>(if (= w 1) (return-from cut-it h))</lang> leads to shown output like

2 x 1: 2     4 x 1: 4


where these rectangles obviously have only 1 symetric cut. As I have no intention to change a language example I cannotdo not intend to run, I just thought to give notice to the author instead. - pKai (talk) 20:44, 10 May 2013 (UTC)

LZW compressor

I have translated your nice C LZW program to D language. I have tried to make it idiomatic D, but some of the C style is probably still present. The D code currently still requires five casts, and I have guarded them with asserts, like:

   assert(tmp >> oBits <= ubyte.max);
   result[outLen] = cast(ubyte)(tmp >> oBits);

Perhaps with some more semantic knowledge of the program it's possible to avoid one or two of those casts. If you want you can tell me if you see something that could be improved in the D version of the code. In some cases it's nice to receive a little of code review on Rosettacode.

Since LZW deals with bit streams of variable-length token, a few casts are probably inevitable. I know nothing about D language, so I can't honestly comment on the D code, but since the C code is so messy, anything you did there would likely be an improvement in terms of safety and readability. If I get the time, it'd probably be a better idea for me to rewrite the C code cleanly instead. --Ledrug (talk) 17:36, 16 May 2014 (UTC)

Finding pi using MonteCarlo method C Implementation

I didn't know if you were tracking the discussion page so I decided to copy our conversation. I hope you don't mind:

Randomly throwing a point in a square, and it has chance p of being in the circle, while (1-p) chance of otherwise. If you throw N points and count the number of times n that they landed in the circle, n would follow wp:binomial distribution (look up the variance formula there). Here we are taking p = n/N as the ratio between areas of circle and square, but n is subject to statistical fluctuation. Assuming that we had the senses to throw a large enough N so n/N wouldn't be a completely bogus estimate of p, but we'd still like to know how far off it could be from p's true value. This is where the variance comes in: it tells you, given N and a rough knowledge of p, how much uncertainty of n (and p) one should expect.
If you want to use the stddev formula, then each takes the value of either 1 (landing in circle) or 0 (not). The average is as mentioned above; now . Note that there are going to be about of those s with value , and with value , so . See how it comes back to the same formula? --Ledrug (talk) 06:17, 5 May 2014 (UTC)
Thank you very much that explains the origin of the formula. Even though following your reasoning the formula should be:
But because we have a factor of we must take into account, then the resulting stddev should be:
Meaning that the formula implemented has an extra factor of inside the square root and a factor of outside of the square root, meaning:
error = val * sqrt(val * (1 - val) / sampled) * 4, when it should be:
error = sqrt(val * (1 - val)) * 4;
Am I missing something else here? Sorry for the intrigue I'm no expert in probability, but I'm curious as to the implementation.-Chibby0ne (talk) 17:18, 17 May 2014 (UTC)
--00:17, 18 May 2014 (UTC)
What I wrote above was only to demonstrate how comes about; it's not actually how variance is derived. For that you need to take the binomial distribution, and calculate the variance of observed (see wp:Variance#Binomial_distribution). When you throw events, and receive positives, the variance of is . Without getting into too much details, let's say your result really means , which leads to , i.e., error = sqrt(val*(1 - val)/sampled)*4. I must admit that the first val in the original code is spurious; I don't know what I was thinking. But that shouldn't give an error that's off by orders of magnitude.
As a rule of thumb, sum of random samples deviates from "true" value by , while mean of random samples deviates by , as long as the distribution is something reasonable. This is why repeating an experiment many times reduces statistical uncertainty, but repeating too many times might not be worth the effort (because of the square root). Now I should go fix the code. --Ledrug (talk) 08:14, 18 May 2014 (UTC)

Topographical Sort

Hi - just wanted to say thanks for doing the C version of the topological sort. I found it to be easier to follow than even some of the other "higher-level" implementations. Also the additional compile levels or layering of dependencies was exactly what I was looking for. Thank you!

Total Area Circle - analytical solution

Hello i am beginning programmer, and your Total Area Circle Analytical solution is exactly what i need to solve a current problem i am working on, but i am working in C++ and cannot follow the Haskell code at all. I would like to ask you for your help writing it in C++, please? This was the only way method i could find to contact you. I hope to hear from you. Thank you. - vballhermie007


Your PostScript entry is short and sweet, but it's not entirely correct. It doesn't fill the pentagon. Fwend (talk) 21:32, 21 April 2015 (UTC)

It depends on what "fill" means. The code before used even-odd winding rule, which may be slightly unusual but I wouldn't exactly call it incorrect. I changed it to produce three different looking stars now, including one that's more likely to meet common expectations. --Ledrug (talk) 08:13, 22 April 2015 (UTC)