The Big Programming Thread - Page 790

Prev 1 788 789 790 791 792 1032 Next

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.

mantequilla

Turkey781 Posts

November 02 2016 21:04 GMT

#15781

cheesy way to count how many times you called the method is to put the variable as instance variable.

other way is to put it as parameter:

recursiveMethod(int count) {
count++;
recursiveMethod(count);
}

ofc first caller will call it as recursiveMethod(0). since most tree algorithms call methods with root as the starting node parameter I think this is ok.

I'm very bad at recursion though. I know everything that can be done recursively can be done iteratively by using a stack.

On November 03 2016 05:24 travis wrote:

Show nested quote +

both, like a mix

im not worth paying for but I may be able to provide some answers if you shoot, in case you don't find someone qualified.

spinesheath

Germany8679 Posts

November 02 2016 21:06 GMT

#15782

You obviously can call a helper method that takes another parameter which just keeps track of the count. But in this case that won't to anything because it's really just the same thing as decreasing "two" by 1 like you do.

Also your code isn't correct yet, it says non-negative, not positive. So both or either number could be 0.

Deleted User 3420

24492 Posts

November 02 2016 21:18 GMT

#15783

oh oops. well im not going to correct it.
and mantequilla I may take you up on it tonight if you are sitll up and I am having problems.

okay so I can pass it as a parameter but then if I do that then yeah I need a helper method. so I am guessing you just can't really keep count without a helper method. which brings us to the next problem I have in the review

Write a recursive method that takes two parameters, a String and a char. The method will count
how many times the char occurs in the String. Hint: You will need to write an auxiliary method
that takes three parameters, one to keep track of what position of the String is currently the
“starting point”

How in the world do I do this??

So I write


	private int charCount(String word, char letter) {
		int position = 0;
		return charCountRecursion(position, word, letter);
		 }

and then I make the helper method


	private int charCountRecursion(int position, String word, char letter) {
                if(word.length < position) {
                  //RETURN WHAT HERE?  how does this work, lol
                }
		if(word.charAt(position) == letter) {
			return charCountRecursion(position + 1, word, letter) + 1;
		}
		return charCountRecursion(position + 1, word, letter) + 1;
	}

edit: the only way I see in my mind of doing this is to actually create a new "word" for each recursive call that is the last word minus the first character. and then the "position" would start at 0 but only increment if the letters matched. which really isn't what the directions say at all.

spinesheath

Germany8679 Posts

November 02 2016 21:41 GMT

#15784

If the character you're looking at is the one you're looking for, return the recursive call + 1, else the recursive call + 0.

You have to think a bit differently for recursion: always first assume that your method already does what it is supposed to do.

Then when you call it for position + 1, you know it will return the number of occurences in the tail of the word starting at position + 1. To get the correct result for your current tail starting at position + 0, you take that and either add 1 or 0 depending on the one letter that is not accounted for.

And if the position exceeds the word length, the letter obviously doesn't occur. Don't think of it as a grand whole. This case only asks how often a letter occurs in an empty word, so you return 0 because that's how it is.

mantequilla

Turkey781 Posts

November 02 2016 21:49 GMT

#15785

something like this maybe? its correct for my 1 string dunno if its totally correct

+ Show Spoiler +

public class RecurS {

public static void main(String[] args) {
System.out.println(new RecurS().charCount("alabama", 'a'));
}

private int charCount(String word, char letter) {
return charCountRecursion(0, word, letter);
}

private int charCountRecursion(int position, String word, char letter) {
if (word.length() <= position) {
return 0;
}

if(word.charAt(position) == letter) {
return 1 + charCountRecursion(position + 1, word, letter);
}

return charCountRecursion(position + 1, word, letter);
}
}

I can't figure out such things without an ide and a debugger

Deleted User 3420

24492 Posts

November 02 2016 21:52 GMT

#15786

ohhh I get it

mantequilla I've gotta go so im not gonna check your code exactly but you basically helped me understand what spinesheat was saying with that code

thanks both

raNazUra

United States10 Posts

November 02 2016 22:29 GMT

#15787

If you're trying to count how many times you've made a recursive call, generally you're just writing a loop in a very awkward way. Also, that hint is not true, it's much easier (and cleaner) to recursively solve this without a helper method. It's possible to do it with a helper, but not necessary.


public int charCount(String str, char c) {
    if (str.length() == 0) {
        return 0;
    }
    else if (str.charAt(0) == c) {
        return 1 + charCount(str.substring(1), c);
    }
    else {
        return charCount(str.substring(1), c);
    }
}

tofucake

Hyrule19237 Posts

November 02 2016 22:47 GMT

#15788

it's actually even simpler than that:


public int charCount(String str, char c) {
    if (str.length() == 0) {
        return 0;
    }
    
    return (int)(str.charAt(0) == c) + charCount(str.substring(1), c);
}

raNazUra

United States10 Posts

November 02 2016 22:55 GMT

#15789

Well sure we can be cleverer than mine.

But I do think there's value in explicitly laying out the logic for someone who's still working on understanding recursion more intuitively. That's my excuse at least

RoomOfMush

1296 Posts

November 02 2016 23:13 GMT

#15790

On November 03 2016 07:47 tofucake wrote:
it's actually even simpler than that:


public int charCount(String str, char c) {
    if (str.length() == 0) {
        return 0;
    }
    
    return (int)(str.charAt(0) == c) + charCount(str.substring(1), c);
}

That doesnt work in java.

spinesheath

Germany8679 Posts

November 02 2016 23:29 GMT

#15791

On November 03 2016 07:47 tofucake wrote:
it's actually even simpler than that:


public int charCount(String str, char c) {
    if (str.length() == 0) {
        return 0;
    }
    
    return (int)(str.charAt(0) == c) + charCount(str.substring(1), c);
}

Don't do that. Don't tell people to do it like that. Especially not in the presence of mostly unspoiled beginners.

Whether this works in your language or not, it's bad. Afaik in C++ it works, but only by convention because the standard doesn't specify that true must be represented by 1. It could just as well be 17657. I don't even want to begin to imagine what Javascript does with that kind of stuff.

In any case though you're casting between two types that are fundamentally incompatible. It makes no sense to say x = 15 + true or Pow(true, 3). Therefore you shouldn't even be allowed to do that in the first place. It's a source of confusion and bugs and a crime on top of that.

dsyxelic

United States1417 Posts

November 03 2016 00:23 GMT

#15792

edit: nvm

Deleted User 3420

24492 Posts

November 03 2016 00:58 GMT

#15793

Is it true that insertion of a new node into a binary search tree always inserts the new node as a leaf?

also, breadth first tree traversal

is this accurate:

you process the root, put it's children into a queue, dequeue the queue, process whatever comes out's children, and repeat until you have processed everything out of the queue?

are you supposed to use recursion to do a breadth first traversal?

tofucake

Hyrule19237 Posts

November 03 2016 01:01 GMT

#15794

On November 03 2016 08:29 spinesheath wrote:

Show nested quote +

On November 03 2016 07:47 tofucake wrote:
it's actually even simpler than that:


public int charCount(String str, char c) {
    if (str.length() == 0) {
        return 0;
    }
    
    return (int)(str.charAt(0) == c) + charCount(str.substring(1), c);
}

yeah crap I keep forgetting travis is using java...

But no, the standard for C++ type conversion is in fact true = 1
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf

4.7
...
4. If the destination type is bool, see 4.12. If the source type is bool, the value false is converted to zero and
the value true is converted to one.

4.12
A prvalue of arithmetic, unscoped enumeration, pointer, or pointer to member type can be converted to a
prvalue of type bool. A zero value, null pointer value, or null member pointer value is converted to false;
any other value is converted to true. For direct-initialization (8.5), a prvalue of type std::nullptr_t can
be converted to a prvalue of type bool; the resulting value is false.

The C99 spec has _Bool true is 1 as well: http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

6.2.5 Types
An object declared as type _Bool is large enough to store the values 0 and 1.

6.3.1.2 Boolean type
When any scalar value is converted to _Bool, the result is 0 if the value compares equal
to 0; otherwise, the result is 1.

edit: we can go deeper

in php, false is 0 and true is 1: http://php.net/manual/en/language.types.integer.php#language.types.integer.casting.from-boolean

in C# (and .Net in general), the syntax is a bit different (have to use ToInt32()), but false is 0 and true is 1: https://msdn.microsoft.com/en-us/library/2cew9dz7(v=vs.110).aspx

In JavaScript, false is 0 and true is 1: https://developer.mozilla.org/en-US/docs/Mozilla/js-ctypes/Using_js-ctypes/Type_conversion

Java doesn't do typecasting like that because everything is a damn object, and that and Perl are the only two languages I know of that force a conditional check to convert.

Blisse

Canada3710 Posts

November 03 2016 03:19 GMT

#15795

On November 03 2016 09:23 dsyxelic wrote:
currently working on an assignment (brute force knight's tour)

my output's wonky though. I get duplicates in random spots

for ex. a 4x4

1 8 3 6
5 5 7 8
9 2 7 4

been debugging for a while and really can't put a finger on it

loops seem to be fine, variables are incrementing correctly
the lists im using are fine

apparently for some of the iterations of the main loop (when I place a marker for knight's position on board), it fills up other parts of the board when it shouldn't be able to. I don't know how, I only have one line that goes like (board[row][col]=marker) in the loop. the marker increments at top of loop.

is there some type of way that the loop can seem like it's working properly but not? I've been putting print statements everywhere. the only thing that's off is that the loop iterates less than the required amount (for a 4x4 it'd be 15 times) which led me to believe that something inside the loop is wrong idk what.

in python btw


while(len(mlist)!=0):
        move+=1 //marker increment
        r = random  //random #, prof wants random bruteforce
        kmove = mlist[r.randrange(0,len(mlist))] //theres a list of possible offsets I have
       //mlist is the list of possible/valid moves for ex. up 1, across 2
    
        board[row+kmove[0]][col+kmove[1]] = move // putting marker
        row += kmove[0]  //update current row
        col += kmove[1]  //update
        
       
       
        del mlist[:]
       
        mlist = validPossibleMoves(row, col, board, vlist) //update mlist
       
        vlist.append([row,col])  //visited list
       
if complete(board):
        status = True

del vlist[:]
vlist = [[0,0]]

You need to post more code but the knights tour isn't possible for 4x4. Your code also won't solve the knights tour anyways because you need to backtrack when you hit a dead end.

I rewrote a bunch of stuff to make things cleaner for myself to debug mostly, but I don't know your validPossibleMoves implementation and your setup before the while loop. I deleted my attempt at it so that's why there's some random boilerplate == True stuff.

I would highly recommend not to "del" things that are used before and after the scope again. It's a bit gross in terms of readability. Also no need to declare a local variable r for random afaik.

http://pastebin.com/XMF4cT97

dsyxelic

United States1417 Posts

November 03 2016 07:42 GMT

#15796

On November 03 2016 12:19 Blisse wrote:

Show nested quote +


while(len(mlist)!=0):
        move+=1 //marker increment
        r = random  //random #, prof wants random bruteforce
        kmove = mlist[r.randrange(0,len(mlist))] //theres a list of possible offsets I have
       //mlist is the list of possible/valid moves for ex. up 1, across 2
    
        board[row+kmove[0]][col+kmove[1]] = move // putting marker
        row += kmove[0]  //update current row
        col += kmove[1]  //update
        
       
       
        del mlist[:]
       
        mlist = validPossibleMoves(row, col, board, vlist) //update mlist
       
        vlist.append([row,col])  //visited list
       
if complete(board):
        status = True

del vlist[:]
vlist = [[0,0]]

thanks, I fixed it a few hours ago tho. the issue was that I had to switch row/col in one of the defs

no backtracking allowed because we were to bruteforce it with random valid moves.
so it was possible to get 0 successes with 1000 attempts , and then get a success with 1 attempt for example

ah thanks, those tips are quite useful for the future

spinesheath

Germany8679 Posts

November 03 2016 08:00 GMT

#15797

On November 03 2016 10:01 tofucake wrote:
0 and 1

I must have been mistaken about the specifications then. Dunno where I got that idea from.

That isn't even my main reason though. The point still stands that bool and int are conceptionally incompatible and should be treated as such.

RoomOfMush

1296 Posts

November 03 2016 09:08 GMT

#15798

On November 03 2016 07:47 tofucake wrote:
[...]

Java doesn't do typecasting like that because everything is a damn object, and that and Perl are the only two languages I know of that force a conditional check to convert.

Thats not true either. All lower-case types like 'boolean' or 'int' are not objects but primitive data types. Boolean is a class and Boolean.TRUE is an object but the literal 'true' is not an object at all.
Besides that, typecasting of objects works in java via compiler magic. The following is typecasting an object into a primitive and it works perfectly fine:

	Integer i = new Integer("5");
	double d = (double) i;

Silvanel

Poland4769 Posts

November 03 2016 15:33 GMT

#15799

On November 03 2016 17:00 spinesheath wrote:

Show nested quote +

Even Python will allow that and Python is pretty hard on implicit type conversion and similiar stuff.
But i generaly agree things like that are kinda like traps for initiated and are potential source of errors.

Deleted User 3420

24492 Posts

November 03 2016 20:15 GMT

#15800

when inserting a node into a binary search tree you only worry about comparing that node to the children, right?

like if the tree is



             11
             /   \
            8    16
          /  \    /  \
         4   9  14  19

and then you insert 17

the new tree would be:



             11
             /   \
            8    16
          /  \    /   \
         4   9  14  19
                       /
                      17

is this correct?

(sorry about formatting, i did my best, it's weirding out. the 17 is the left child of 19)

Prev 1 788 789 790 791 792 1032 Next

Please or register to reply.

The Big Programming Thread - Page 790

Completed

Ongoing

Upcoming