Win a copy of Classic Computer Science Problems in Swift this week in the iOS forum!

Garrett Rowe

Ranch Hand
+ Follow
since Jan 17, 2006
Cows and Likes
Cows
Total received
0
In last 30 days
0
Total given
0
Likes
Total received
20
Received in last 30 days
0
Total given
0
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by Garrett Rowe

I'm not sure if this belongs in this forum, but it is more an algorithm question than a programming, or language specific question.

Given a function that takes 2 integer parameters, f(a, b), it should return a number representing how much you have to add to a to make it a multiple of b.

So:

f(1, 2) = 1
f(2, 2) = 0
f(1, 3) = 2
f(4, 3) = 2
f(5, 3) = 1
f(6, 3) = 0

What I have seems correct, but overly complicated:

f(a, b) = (b - (a % b)) % b

Is there a better cleaner way?
When you say the program doesn't work. What it is currently doing wrong?
6 years ago
Another option would be to compute the Levenshtein distance between the two words and test whether they are sufficiently close.



See Levenshtein distance
6 years ago

Paul Clapham wrote:It can't just be a function of M and N, because (up to isomorphism) there are two different 4-element lists with 2 distinct elements, namely [0, 0, 1, 1] and [0, 1, 1, 1].

And they have different maximum derangements: the first's MD is 4 and the second's is 2.



Good point. I hadn't thought that through.

In general for a list with K zeroes and L ones, where K <= L, the maximum derangement is 2K, unless I'm missing something. But extending that to 3 or more distinct elements isn't nearly as obvious, although I haven't spent any time poking at it.


Unfortunately the problem I was trying to solve might be a bit more difficult. I was looking at the Best Shuffle problem on Rosetta Code and trying to figure out if there is an algorithm for deciding ahead of time the maximum deraingement of the target word. You could then theoretically continuously random shuffle and check until you came up with a permutation with maximum derangement,
For a 2 element list with 2 distinct elements [0, 1] a permutation exists where there all elements are in a different position than the original list. We can say that the maximum "derangement" of the list is 2


For a 3 element list with 2 distinct elements [0, 1, 1] every permutation has at least one element that is in the same position in the permuted list as the original list. The maximum derangement of this list is also 2.


Is there a formula for the generalization of this observation. i.e. for an M element list with N distinct elements (where N <= M) the maximum possible derangement of a permutation of that list is X?

I've tried googling, but I can't come up with the right keywords, and the math quickly goes over my head.
An alternate way to do what you're attempting:



A side benefit of doing it this way, besides being idiomatic, is that the resulting collection is correctly typed as a List[String]
6 years ago
The groupByDate() method takes a List<FormBean> and returns a Map<Date, List<FormBean>>, you can use this data structure as-is or optionally transform it into a List<List<FormBean>> where every element in each sub-list has the same Date.
6 years ago
How about something like:


It might be more flexible if requirements change in the future.
6 years ago
I'll do 12.

7 years ago
We're getting into spoiler alert territory here. My solution would have been nice if I could have come up with a nicer algorithm for my transposeDiagonal function. But quick & dirty:
7 years ago
OK, I'll chime in. I won't do number 10 since it's trivial if you use your Sieve function, but I will post my version of the sieve. I use the same algorithm as Luigi, but it's a few lines shorter.

7 years ago
You added the "wrong lines". I think you have to assume classes A and B exist. In that case the only way the code will compile is if B extends A (google java covariant return type).

7 years ago
I haven't implemented one so I don't know the pitfalls, but a DAWG might be useful for this problem.
7 years ago

Campbell Ritchie wrote:
The remove() method should remove.


Or throw an UnsupportedOperationException as the OP has done. The remove method is documented as optional (and it can be argued should have never been part of the Iterator interface to begin with).
7 years ago

David Newton wrote:I'm pretty sure I can handle specs.


Ah, so you've broken the code! :) Although I should have known better than to question your abilities since you mention you're a 'Polyglottal Developer' right in your signature.

(No sense in declaring "expected", though, and it makes the test harder to read. Plus you don't always use it anyway.)


You're right of course. Point taken.

TDD and BDD are the same: write the most minimal test case that fails, write the code to make it pass. The output of a program is a large-scale behavior, and tests written for it will not pass until the sub-behaviors pass. That you were writing the large-scale behavior test first suggests you either (a) didn't test during development, or (b) expected it to fail for a long time while the actual code was developed.


The answer is (b). The way I decide what low-level behaviors to implement is to start with the high level abstraction, and then break that down into smaller and smaller problems until I get to a problem I can implement. What I like about the top-down approach is that I feel like it keeps me focused. The problem with that approach is that as you pointed out the tests will fail for a long time. (I'm sure there are other problems too, but that is the most obvious one to me).
7 years ago