digitalmars.D.learn - Palindromes
- Jim Barnett (34/34) Dec 03 2015 TL;DR I couldn't figure out how to write `isPalindrome` in terms
- Justin Whear (10/19) Dec 03 2015 I don't think you want reverse because it works in-place; you'd need to
- Jim Barnett (4/13) Dec 03 2015 Awesome, and thank you! Clearly I need to learn more about the D
- =?UTF-8?B?Tm9yZGzDtnc=?= (44/45) Dec 03 2015 My version slightly adjusted version:
- Jim Barnett (9/55) Dec 03 2015 Interesting solution... probably worth some future analysis for
- Jim Barnett (2/4) Dec 03 2015 Sorry, inside the `while` loop
- Meta (4/9) Dec 03 2015 In D it's considered idiomatic, but it can also cause some very
- Jim Barnett (5/15) Dec 03 2015 Really? If it leads to "hard to detect errors", I have a hard
- Meta (35/40) Dec 03 2015 It's used throughout the standard library, granted I don't think
- Jim Barnett (7/13) Dec 03 2015 That's interesting food for thought. At this point, I am just
- Brad Anderson (8/18) Dec 03 2015 Inside a while, I don't think, really matches the idiom's goals.
- =?UTF-8?Q?Ali_=c3=87ehreli?= (26/27) Dec 03 2015 In addition to what others have explained, local imports are necessary
TL;DR I couldn't figure out how to write `isPalindrome` in terms
of std.algorithm.mutation.reverse
I have dabbled in D a few times over the past few years, but
still pretty inexperienced. I decided to work on some project
euler problems in D for fun. A problem requires detecting a
palindrome. I solved this problem in C++ before with this:
bool is_palindrome(const string& str)
{
return str == string(str.rbegin(), str.rend());
}
I found Andrei's response to a stackoverflow question here:
http://stackoverflow.com/questions/14469612/template-conflict-for-palindrome-algorithm-on-string-array
In his response, he suggests this:
bool isPalindrome(Range)(Range r)
{
while (!r.empty) {
if (a.front != a.back) {
return false;
}
r.popFront();
if (r.empty) {
return true;
}
r.popBack();
}
return true;
}
I recognize it's more efficient in terms of CPU time and memory
than my C++ solution, but I suspect there is a shorter expression
to detect palindromes if efficiency isn't the primary concern. So
I am interested in seeing implementations of `isPalindrome` that
utilize `std.algorithm.mutation.reverse`, or anyone who cares to
enlighten me why that might be a misguided thing to want. Thanks
for reading.
Dec 03 2015
On Thu, 03 Dec 2015 21:40:05 +0000, Jim Barnett wrote:TL;DR I couldn't figure out how to write `isPalindrome` in terms of std.algorithm.mutation.reverse I recognize it's more efficient in terms of CPU time and memory than my C++ solution, but I suspect there is a shorter expression to detect palindromes if efficiency isn't the primary concern. So I am interested in seeing implementations of `isPalindrome` that utilize `std.algorithm.mutation.reverse`, or anyone who cares to enlighten me why that might be a misguided thing to want. Thanks for reading.I don't think you want reverse because it works in-place; you'd need to make a copy to compare against. std.range.retro is probably what you're looking for: bool isPalindrome(R)(R range) if (isBidirectionalRange!R) { return range.equal(range.retro); } Obviously this does more work than strictly necessary, but has the brevity you're looking for.
Dec 03 2015
Jim Barnett <james.barnett.jr gmail.com>
On Thursday, 3 December 2015 at 22:14:02 UTC, Justin Whear wrote:
I don't think you want reverse because it works in-place; you'd
need to make a copy to compare against. std.range.retro is
probably what you're looking for:
bool isPalindrome(R)(R range) if (isBidirectionalRange!R)
{
return range.equal(range.retro);
}
Obviously this does more work than strictly necessary, but has
the brevity you're looking for.
Awesome, and thank you! Clearly I need to learn more about the D
type system and std.range, but this is exactly the type of answer
is was looking for.
Dec 03 2015
On Thursday, 3 December 2015 at 21:40:05 UTC, Jim Barnett wrote:Thanks for reading.My version slightly adjusted version: /** Returns: If range is a palindrome larger than $(D minLength). See also: http://forum.dlang.org/thread/dlfeiszyweafpjiocplf forum.dlang.org#post-vpzuaqxvtdpzpeuorxdl:40forum.dlang.org See also: https://stackoverflow.com/questions/21849580/equality-operator-in-favour-of-std-range-equal TODO: Test graphemes in `string` and `wstring`. */ bool isSymmetric(R)(R range, size_t minLength = 0) // TODO good value for minLength? if (isBidirectionalRange!(R)) { static if (isRandomAccessRange!R) // arrays excluding `char[]` and `wchar[]` { if (range.length < minLength) { return false; } } size_t i = 0; while (!range.empty) { import std.range.primitives: front, back, popFront, popBack; if (range.front != range.back) return false; range.popFront(); i++; if (range.empty) break; range.popBack(); i++; } return i >= minLength; } unittest { assert(`dallassallad`.isSymmetric); assert(!`ab`.isSymmetric); assert(`a`.isSymmetric); assert(`åäå`.isSymmetric); assert(`áá`.isSymmetric); assert(`åäå`.isSymmetric(3)); assert(!`åäå`.isSymmetric(4)); assert(``.isSymmetric); assert([1, 2, 2, 1].isSymmetric); assert(![1, 2, 2, 1].isSymmetric(5)); } alias isPalindrome = isSymmetric;
Dec 03 2015
On Thursday, 3 December 2015 at 23:42:31 UTC, Nordlöw wrote:On Thursday, 3 December 2015 at 21:40:05 UTC, Jim Barnett wrote:Interesting solution... probably worth some future analysis for me... The `import` statement inside the `for`-loop kind of smells to me. It's a little more generalized than I was looking for, but interesting. Your code is also searching for a threshold of symmetry. I haven't encountered a problem like that personally, but it's interesting and makes me think. I appreciate your response.Thanks for reading.My version slightly adjusted version: /** Returns: If range is a palindrome larger than $(D minLength). See also: http://forum.dlang.org/thread/dlfeiszyweafpjiocplf forum.dlang.org#post-vpzuaqxvtdpzpeuorxdl:40forum.dlang.org See also: https://stackoverflow.com/questions/21849580/equality-operator-in-favour-of-std-range-equal TODO: Test graphemes in `string` and `wstring`. */ bool isSymmetric(R)(R range, size_t minLength = 0) // TODO good value for minLength? if (isBidirectionalRange!(R)) { static if (isRandomAccessRange!R) // arrays excluding `char[]` and `wchar[]` { if (range.length < minLength) { return false; } } size_t i = 0; while (!range.empty) { import std.range.primitives: front, back, popFront, popBack; if (range.front != range.back) return false; range.popFront(); i++; if (range.empty) break; range.popBack(); i++; } return i >= minLength; } unittest { assert(`dallassallad`.isSymmetric); assert(!`ab`.isSymmetric); assert(`a`.isSymmetric); assert(`åäå`.isSymmetric); assert(`áá`.isSymmetric); assert(`åäå`.isSymmetric(3)); assert(!`åäå`.isSymmetric(4)); assert(``.isSymmetric); assert([1, 2, 2, 1].isSymmetric); assert(![1, 2, 2, 1].isSymmetric(5)); } alias isPalindrome = isSymmetric;
Dec 03 2015
On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:The `import` statement inside the `for`-loop kind of smells to me.Sorry, inside the `while` loop
Dec 03 2015
On Friday, 4 December 2015 at 00:26:23 UTC, Jim Barnett wrote:On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:In D it's considered idiomatic, but it can also cause some very hard to detect errors from time to time... I hate it for this reason and never do it in my own code.The `import` statement inside the `for`-loop kind of smells to me.Sorry, inside the `while` loop
Dec 03 2015
On Friday, 4 December 2015 at 00:50:17 UTC, Meta wrote:On Friday, 4 December 2015 at 00:26:23 UTC, Jim Barnett wrote:Really? If it leads to "hard to detect errors", I have a hard time believing that can be "idiomatic D". I have never seen a language that encourages the user to specify dependencies inside a loop. I am hoping I misunderstood something here.On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:In D it's considered idiomatic, but it can also cause some very hard to detect errors from time to time... I hate it for this reason and never do it in my own code.The `import` statement inside the `for`-loop kind of smells to me.Sorry, inside the `while` loop
Dec 03 2015
On Friday, 4 December 2015 at 01:10:41 UTC, Jim Barnett wrote:Really? If it leads to "hard to detect errors", I have a hard time believing that can be "idiomatic D".It's used throughout the standard library, granted I don't think there's any occurrences of importing inside a while loop. The issues with nested imports are well known but also hard to fix without breaking code. However, they cut down on template bloat and the standard library makes very heavy use of templates. Thus a tradeoff is made. It's usually not nested imports by themselves that create these hard to detect errors, however. It's a few different D features working in concert. Observe the following code: struct Test { int num = 1; string text = `"this is a line of text"`; void printMessage() { import std.conv, std.stdio; writeln(text("My text is ", text, " and my num is ", num)); } } void main() { Test t; t.printMessage(); } It prints: "My text is and my num is 0" Why the empty space? Because instead of referring to this.text inside of the printMessage method, `text` refers to std.conv.text. The nested import overrides the member variable in the outer scope.I have never seen a language that encourages the user to specify dependencies inside a loop. I am hoping I misunderstood something here.Sorry, I thought you were referring more generally to nested imports. No, imports in a while loop are not encouraged; imports in a struct or a template are.
Dec 03 2015
On Friday, 4 December 2015 at 03:33:55 UTC, Meta wrote:That's interesting food for thought. At this point, I am just trying trying to transliterate my C++ and Ruby solutions for project Euler problems to D, and trying to get a better grasp on the D type system. Compile-time optimization isn't of much interest to me right now, but I am glad you pointed out that is something else to consider.I have never seen a language that encourages the user to specify dependencies inside a loop. I am hoping I misunderstood something here.Sorry, I thought you were referring more generally to nested imports. No, imports in a while loop are not encouraged; imports in a struct or a template are.
Dec 03 2015
On Friday, 4 December 2015 at 00:50:17 UTC, Meta wrote:On Friday, 4 December 2015 at 00:26:23 UTC, Jim Barnett wrote:Inside a while, I don't think, really matches the idiom's goals. By only sticking imports inside the code that makes use of them you can achieve (I've never measured it though) compilation performance improvements in code that then imports the containing module but never makes use of the code in question. Sticking the import in the middle of the code is just noisy though, you want it nearby with limited scope but otherwise out of the way.On Friday, 4 December 2015 at 00:23:45 UTC, Jim Barnett wrote:In D it's considered idiomatic, but it can also cause some very hard to detect errors from time to time... I hate it for this reason and never do it in my own code.The `import` statement inside the `for`-loop kind of smells to me.Sorry, inside the `while` loop
Dec 03 2015
On 12/03/2015 04:23 PM, Jim Barnett wrote:The `import` statement inside the `for`-loop kind of smells to me.In addition to what others have explained, local imports are necessary for template mixins: http://ddili.org/ders/d.en/mixin.html#ix_mixin.import,%20local Quoting: module a; import std.string; // ← wrong place mixin template A(T) { string a() { T[] array; // ... return format("%(%s, %)", array); } } "if std.string is not imported at the actual mixin site, then the compiler would not be able to find the definition of format() at that point" module a; mixin template A(T) { string a() { import std.string; // ← right place T[] array; // ... return format("%(%s, %)", array); } } Ali
Dec 03 2015