|
Thread Rules
1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution.
2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20)
3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible.
4. Use [code] tags to format code blocks. |
We had a few non-graded java recursion exercises on a handout today
one of them was to: "given a string, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*"
for example, aabba would be ---> a*ab*ba
Wanted to know how any of you would do that. Here is my code if there are any critiques
private static String temp;
private static String newString = "";
public static String pairStar(String str) {
if(str.length() == 1) {
newString = newString + str;
return newString;
}
if(str.charAt(0) == str.charAt(1)) {
temp = str.charAt(0) + "*";
} else {
temp = Character.toString(str.charAt(0));
}
newString = newString + temp;
if(str.length() > 1) {
pairStar(str.substring(1));
}
return newString;
}
|
Just a note that I'm not sure using static variables totally counts as recursion. The approach looks good though I have styling preferences.
Also would crash on empty string.
Don't need the temp variable, just append directly.
Would recommend StringBuilder.
|
While this is technically recursive, you still use those temp and newString variables outside of your recursion. Usually the solution that is aimed at with these kinds of excercises want you to solve the whole problem in the recursion itself; in a kind of functionally way. This means that your recursive function should have no side effects. I think the desired solution should only use input parameters, local variables and the return parameter.
Here is some pseudo code that might help you:
star(string):
if string.length == 1
return string
else
return star(string.first, string.rest)
star(char, string):
if char == string.frist
return char + "*" + star(string)
else
return char + star(string)
Notice that we have two overloads of the function "char":
- One with one parameter named string
- One with two parameters named char and string
Do not confuse the names with java types. I would strongly recommend you use only the type String in your solution. :-)
I guess this solution leaves something for discussion: Some people might find the indirect recursion (two functions call each other recursively) too difficult to understand and might want to write it all in one function.
|
I tend to do recursion until 0, [] or "" for that very reason. I also agree with blisse that using a field to store your return value in is cheating.
I would probably do it as follows:
recursivestring(teststring);
String recursivestring(test) {
if test == null or test.size() = 0 return "";
else {
Char s = test.charAt(0)
String result = recursivestring(test.substring(1, test.size());
if result.size() = 0 return s;
if s.equals(result.charAt(0))
result = s + "*" + result;
else
result = s + result;
return result;
}
But in proper Java, rather than shitty pseudocode that i mashed up on my phone.
Ninja'd
|
On October 25 2016 07:59 travis wrote:We had a few non-graded java recursion exercises on a handout today one of them was to: "given a string, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*" for example, aabba would be ---> a*ab*ba Wanted to know how any of you would do that. Here is my code if there are any critiques + Show Spoiler +
private static String temp;
private static String newString = "";
public static String pairStar(String str) {
if(str.length() == 1) {
newString = newString + str;
return newString;
}
if(str.charAt(0) == str.charAt(1)) {
temp = str.charAt(0) + "*";
} else {
temp = Character.toString(str.charAt(0));
}
newString = newString + temp;
if(str.length() > 1) {
pairStar(str.substring(1));
}
return newString;
}
Yeah, like Blisse, I'm not sure that using static variables would be ok. Technically, you're still using recursion, since you call the function from within itself, but it's not the cleanest solution.
public static String pairStar(String str) {
if (str.length() <= 1) {
return str;
}
if (str.charAt(0) == str.charAt(1)) {
return str.charAt(0) + "*" + pairStar(str.substring(1));
}
else {
return str.charAt(0) + pairStar(str.substring(1));
}
}
That would be the classic recursion way for me. You could make it a bit more concise:
public static String pairStar(String str) {
if (str.length() <= 1) {
return str;
}
String matchChar = str.charAt(0) == str.charAt(1) ? "*" : ""; // Or whatever Java's ternary operator is
return str.charAt(0) + matchChar + pairStar(str.substring(1));
}
and you could do some stuff to make it tail-recursive, but I'm not sure if Java is able to take advantage of that?
EDIT: AKnopf, I'm curious why you would use indirect recursion on a simple problem like this. Is there an inherent advantage to it, or do you just tend towards that kind of solution? Just curious.
|
public static String parseStr(String str) {
if (str == null) {
return "";
}
if (str.length() < 2) {
return str;
}
if (str.charAt(0) == str.charAt(1)) {
return str.charAt(0) + "*" + parseStr(str.substring(1));
}
return str.charAt(0) + parseStr(str.substring(1));
}
and you could do some stuff to make it tail-recursive, but I'm not sure if Java is able to take advantage of that?
AFAIK Java doesn't support TRE. But that might've changed.
|
Java doesn't support TCO and won't anytime soon.
Using a functional language:
let pair() =
let rec pair_r(s: char list)(acc: char list) =
match s with
| a :: b :: xs ->
if a = b then pair_r s.Tail ('*' :: a :: acc) else pair_r s.Tail (a :: acc)
| [a] -> a :: acc
| [] -> acc
pair_r ['A'; 'A'; 'B'; 'C'; 'C'; 'D'] [] |> List.rev
Which is more elegant in my opinion (and tail recursive).
PS: Normally, you would use a foldr though.
|
On October 25 2016 10:24 Hhanh00 wrote:Java doesn't support TCO and won't anytime soon. Using a functional language:
let pair() =
let rec pair_r(s: char list)(acc: char list) =
match s with
| a :: b :: xs ->
if a = b then pair_r s.Tail ('*' :: a :: acc) else pair_r s.Tail (a :: acc)
| [a] -> a :: acc
| [] -> acc
pair_r ['A'; 'A'; 'B'; 'C'; 'C'; 'D'] [] |> List.rev
Which is more elegant in my opinion (and tail recursive). PS: Normally, you would use a foldr though.
Yes. None of that exists in Java, though.
In general, I think learning/teaching recursion in Java is pretty shitty and I would never program the simple string replacement thingy like that in Java using recursion. Yes, it's possible, but it is clunky in comparison to a simple loop, and almost certainly far far slower as well. Whereas if you learn recursion in a language that was actually designed for it (I learned in Haskell), you can appreciate the elegance and power of the method. And then you learn about folds and your mind is blown completely (and your code will never ever be legible again to anybody).
|
I did not expect that last line lol
|
I did a bit of experimentation out of curiosity:
public static String star(String s, String r) {
if (s.length() < 2) {
return r.length() == 0 ? s : r + s;
}
if (s.charAt(0) == s.charAt(1)) {
return star(s.substring(1), r + s.charAt(0) + "*");
}
return star(s.substring(1), r + s.charAt(0));
}
^ This is more elegant but produces 117 calls.
public static String star(String s) {
if (s.length() < 2) {
return s;
}
if (s.charAt(0) == s.charAt(1)) {
return s.charAt(0) + "*" + star(s.substring(1));
}
return s.charAt(0) + star(s.substring(1));
}
The uglier thing does only 87 calls.
Both tested with just "aabba".
I guess the difference is in the ternary operator. Not sure how to get rid of it though...
|
I've tried a few variations and compared them to the last posted, i.e. Manit0u's, since I was bored at work (tomorrow is my last day at my current job):
package test;
class Test
{
private static String StarStringBuilder(String input, int index, StringBuilder output)
{
if (index >= input.length()) return output.toString();
if (index > 0 && input.charAt(index) == input.charAt(index - 1))
{
output.append('*');
}
return StarStringBuilder(input, index + 1, output.append(input.charAt(index)));
}
private static String StarString(String input, int index, String output)
{
if (index >= input.length()) return output;
if (index > 0 && input.charAt(index) == input.charAt(index - 1))
{
output += '*';
}
return StarString(input, index + 1, output + input.charAt(index));
}
public static String Manit0uStar2(String s) {
if (s.length() < 2) {
return s;
}
if (s.charAt(0) == s.charAt(1)) {
return s.charAt(0) + "*" + Manit0uStar2(s.substring(1));
}
return s.charAt(0) + Manit0uStar2(s.substring(1));
}
public static String Manit0uStar1(String s, String r) {
if (s.length() < 2) {
return r.length() == 0 ? s : r + s;
}
if (s.charAt(0) == s.charAt(1)) {
return Manit0uStar1(s.substring(1), r + s.charAt(0) + "*");
}
return Manit0uStar1(s.substring(1), r + s.charAt(0));
}
public static void main(String[] args)
{
long startTime = 0;
long endTime = 0;
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
StarStringBuilder("aabba", 0, new StringBuilder());
}
endTime = System.currentTimeMillis();
System.out.printf("StringBuilder: ").println(endTime - startTime);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
StarString("aabba", 0, "");
}
endTime = System.currentTimeMillis();
System.out.printf("String: ").println(endTime - startTime);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
Manit0uStar1("aabba", "");
}
endTime = System.currentTimeMillis();
System.out.printf("Manit0u 1: ").println(endTime - startTime);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
Manit0uStar2("aabba");
}
endTime = System.currentTimeMillis();
System.out.printf("Manit0u 2: ").println(endTime - startTime);
}
}
Result:
StringBuilder: 27
String: 44
Manit0u 1: 67
Manit0u 2: 82
StringBuilders are good.
|
Except that you're doing this in Java with static input. The whole inner block can theoretically be optimized away entirely for all these loops (determine that there are no side effects and the return value is never used). At the very least the JIT and Branch Predictor will mess you up big time. In other words: This performance data is not representative.
|
On October 25 2016 22:32 spinesheath wrote:
Except that you're doing this in Java with static input. The whole inner block can theoretically be optimized away entirely for all these loops (determine that there are no side effects and the return value is never used). At the very least the JIT and Branch Predictor will mess you up big time. In other words: This performance data is not representative.
Ok, static input removed, I'm now using a randomly generated string of 100 characters length.
public static void main(String[] args)
{
long startTime = 0;
long endTime = 0;
int count = 0;
Random random = new Random();
StringBuilder randomStringBuilder = new StringBuilder();
for (int i = 0; i < 100; ++i)
{
randomStringBuilder.append((char)(random.nextInt(26) + (int)'a'));
}
String randomString = randomStringBuilder.toString();
System.out.println(randomString);
String check = StarStringBuilder(randomString, 0, new StringBuilder());
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
if (StarStringBuilder(randomString, 0, new StringBuilder()).equals(check))
{
++count;
}
}
endTime = System.currentTimeMillis();
System.out.printf("StringBuilder: ").println(endTime - startTime);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
if (StarString(randomString, 0, "").equals(check))
{
++count;
}
}
endTime = System.currentTimeMillis();
System.out.printf("String: ").println(endTime - startTime);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
if (Manit0uStar1(randomString, "").equals(check))
{
++count;
}
}
endTime = System.currentTimeMillis();
System.out.printf("Manit0u 1: ").println(endTime - startTime);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; ++i)
{
if (Manit0uStar2(randomString).equals(check))
{
++count;
}
}
endTime = System.currentTimeMillis();
System.out.printf("Manit0u 2: ").println(endTime - startTime);
System.out.println(StarStringBuilder(randomString, 0, new StringBuilder()).equals(StarString(randomString, 0, "")));
System.out.println(StarString(randomString, 0, "").equals(Manit0uStar1(randomString, "")));
System.out.println(Manit0uStar1(randomString, "").equals(Manit0uStar2(randomString)));
System.out.println(StarStringBuilder(randomString, 0, new StringBuilder()));
System.out.println(count);
}
Result:
qqzbgxoksvandahebthhpoxhiuiwfoxijgveoidclxudatdpolqilkjokwvlxdriblhwfdqsczmnjcxchtuefqdcxhkigvglqjin
StringBuilder: 107
String: 1205
Manit0u 1: 1134
Manit0u 2: 867
true
true
true
q*qzbgxoksvandahebth*hpoxhiuiwfoxijgveoidclxudatdpolqilkjokwvlxdriblhwfdqsczmnjcxchtuefqdcxhkigvglqjin
400000
|
That's still a static input in the context of the loops.
|
Heh, just for fun:
<?php
function star($str)
{
return preg_replace_callback('/(.)\1+/', function($matches) {
return implode('*', str_split($matches[0], 1));
},
$str
);
}
$start = getrusage();
echo star('aabba') . PHP_EOL;
$end = getrusage();
function getRuntime($start, $end, $measurement)
{
return ($end["ru_{$measurement}.tv_sec"] * 1000 + intval($end["ru_{$measurement}.tv_usec"] / 1000))
- ($start["ru_{$measurement}.tv_sec"] * 1000 + intval($start["ru_{$measurement}.tv_usec"] / 1000));
}
echo "Process took ".getRuntime($start, $end, 'utime')."ms for computations".PHP_EOL;
echo "Process spent ".getRuntime($start, $end, 'stime')."ms in system calls".PHP_EOL;
// ---- OUTPUT ----
a*ab*ba
Process took 0ms for computations
Process spent 0ms in system calls
Does Java have equivalent of preg_replace_callback() from PHP?
|
Lol. Travis, were you expecting this? :D
|
On October 25 2016 22:59 Acrofales wrote:
Lol. Travis, were you expecting this? :D
Hehe. I guess that no one could've predicted that 
Also, I've learned today that JVM has full support for dynamic typing, TCO and other funky shit - just not for Java 
|
lol no this is great, love the participation.
I'll post the "hard" exercise that was included since you guys seem to enjoy this. I haven't tried it yet, I might this weekend but now I have to study for my calc 2 exam until friday.
Hard exercise:
Your method parameter is an array of ints. The method is a boolean. The goal is to look at the ints and see if you could possibly return 2 arrays from it, both having the same "total" within it.
For example if you were passed {2, 2} it would be true. {2, 3, 2, 3} would be true. {2, 3} would be false. {5, 2, 3} would be true. {5, 2, 4} would be false. {2, 6, 2, 2} would be true. Etc. Have fun!
Oh and it's supposed to use recursion, so no loops. You can make a recursive helper method, though.
|
On October 25 2016 23:26 Manit0u wrote:Show nested quote +On October 25 2016 22:59 Acrofales wrote:
Lol. Travis, were you expecting this? :D Hehe. I guess that no one could've predicted that Also, I've learned today that JVM has full support for dynamic typing, TCO and other funky shit - just not for Java
JVM has no support for TCO. In Scala, TRE is done by the compiler but does not cover mutual recursion. That's why there are trampolines in scalaz.
|
On October 25 2016 23:40 Hhanh00 wrote:Show nested quote +On October 25 2016 23:26 Manit0u wrote:On October 25 2016 22:59 Acrofales wrote:
Lol. Travis, were you expecting this? :D Hehe. I guess that no one could've predicted that Also, I've learned today that JVM has full support for dynamic typing, TCO and other funky shit - just not for Java JVM has no support for TCO. In Scala, TRE is done by the compiler but does not cover mutual recursion. That's why there are trampolines in scalaz.
But from what I've read most of the recursion in scala is translated into loops anyway.
|
|
|
|
|
|
EPT
