24
There are four other answers here, and they all have very sensible advice. But none of them, as far as I can see, points out the terrible runtime complexity of the chosen algorithm, so I think an additional answer is necessary.
1. Bug
>>> english_words = set('bar bat cat war'.split())
>>> transform(english_words, 'bar', 'war', 0)
['bar', '...
15
Always Return An Answer
Whenever you're writing an algorithm, it should return the answer. Not print and return, not just print. Just return. If you want to print, you can always write print some_algo(...).
is_diff_one
We can write this a little cleaner. There is a zip() function in the Python standard library that can walk multiple iterables at once. (...
15
1. Review
The problem of putting the tickets in order is the same as that of constructing an Eulerian path on the directed graph whose edges correspond to the tickets. (An Eulerian path is a path in a graph that follows every edge exactly once.)
Since this is really a graph problem, it would make things clearer if the code used graph terminology rather ...
13
Welcome to Code Review. This post is a mixture between review, remarks, tutorial and general guidelines. Overall, your code has two complexity issues: space complexity due to types (see "Tip: Use implicit data") and algorithmic complexity due to algorithms (see "Diagonals"). Several of your references should be const (see "Tip: Use const Type& if you don'...
10
I find this a nice piece of code.
Still I found 1 minor and 1 bigger issue.
Bigger issue :
You say in the javadoc that if more then 1 bassin is found the biggest must be returned.
You implement nice testing but this I don't find back in the testings.
All your testings have 1 lowest bassin.
I should add this to the test :
@Test
public void ...
9
Very nice:
Few minor changes I would make.
In isAvailable() I would check row/col/box all at the same time.
int isAvailable(int sudoku[][9], int row, int col, int num)
{
//checking in the grid
int rowStart = (row/3) * 3;
int colStart = (col/3) * 3;
int i, j;
for(i=0; i<9; ++i)
{
if (sudoku[row][i] == num) ...
7
This is not C++. This is C. I suspect the only reason you label it as C++ code is because you needed to use a map.
Don't use C-style headers. <cstdio> instead of <stdio.h>. Don't use <cstdio>, use <iostream>.
Macros are bad. They give horrible error messages, don't follow scoping rules, and confuse the reader.
a. What can MAX mean? ...
7
private final
I think this is not the first time I'm telling you this. The ints in your enum really should be private final (At least final!)
int rowDelta;
int colDelta;
Consider the code: Direction.S.rowDelta = 42; // OOPS!
That said, I think your Direction enum is good enough to be public. This is not the first time I see you use this enum. You're not ...
6
I'm sorry, but that code is really convoluted.
First off, does this actually work? The comparisons direction == "N"(etc.) should fail at compile time due to incomparable types (String and StringBuilder) and nDir.equals("") would always return false.
Generally you can't use use == to compare strings in Java. You have to use equals (for strings. ...
6
Instead of using a fixed order of filling in cells you can first take the cells with the least amount of options left.
In other words if you know that cell 5,8 can only contain 5 and 6 then try each of them now and reduce the possibilities of the other cells instead of having to come back millions of times just to find out that the cell can't be filled any ...
6
General remarks
chessBoard, size, boundary and noOfBacktrackCalls should be non-static and private -- since the functions manipulating them are also (correctly!) non-static.
Naming: I suggest rowOrColHasAQueen instead of rowAndColhasAQueen (also note capitalization)
Pre-condition checking: at the beginning of backTrackRoutine, I suggest checking also that ...
6
First, your indentation is a little crazy, which makes it very difficult to see which code is in which scope. Consider:
if ( queens_row_num[j] )
{
if ( std::abs(queens_row_num[j] - row) ==
std::abs(j - col) ||
queens_row_num[j] == row || j == col )
return true;
}
compared to:
if (queens_row_num[j])
{
if (std::abs(queens_row_num[j]...
6
I am unfamiliar with both the design pattern and the backtracking algorithm, so almost all of my comments will be nitpicks.
utils.py
kk_sub: I prefer values[0] - values[1] in {value, -value}, which will work if value is negative. Maybe we know that it will always be nonnegative, though.
kk_div: I prefer values[0] == values[1] * value or values[1] == values[...
6
One option that might help speed things up would be to include a bit of redundant metadata with your board. Rather than just representing an array of 8*8 Booleans representing whether a Queen is in play on a given cell, you could also have 8 Boolean arrays indicating whether a Queen is in play anywhere on a given row, column, or diagonal. That would make it ...
5
Since you said you were looking for suggestions for coding style I will focus on that.
Comment your code! Preferably with Haddock style comments. Even if you aren't planning on sharing your code with others, having comments will still help you if you decide to come back to a project after a break.
Haddock is a system that will automatically generate ...
5
I will answer an isomorphous question of finding a minimal value in a binary tree. In your case, the tree is octal, but the same rules apply.
Consider that you have
typedef struct node {
struct node *pLeft, *pRight;
int value;
} node_t;
The tree is completely unsorted, and you need to find the minimal value. What you are doing is something like ...
5
In Python, strings support the sequence interface, so you can write the vowels and consonants as strings, which are easier to read than lists:
vowels = 'aeiou'
consonants = 'bcdfghjklmnpqrstvxz'
Writing out the consonants explicitly like this is risky: it would be easy to omit one and not notice. (What happened to w and y?) It would be more reliable to ...
5
Since you don't seem to be concerned with the order of any of the collections of objects you use, only membership in those collections, Set is probably the better Collection to use, instead of List. I imagine that Set.contains is going to be more efficient than List.contains.
Also, it's not clear to me that recursion is the way to go here. If I were you, ...
5
static int size = 6;
This should be final, as you don't change it.
boolean flag = false;
noOfBacktrackCalls++;
if (!isMoveSafe(row, col)) {
return false;
}
move++;
chessBoard[row][col] = move;
if (move == size * size) {
return true;
}
flag = true;
You ...
5
Besides what Hosch250 said, with all of which I agree, here are a few more C++ style points:
#include <cmath>
You don't use anything from <cmath>, but you do use std::abs, which is located in <cstdlib>.
const int row_size, col_size;
const int row_queen, col_queen;
It is generally considered bad style to declare multiple entities on the ...
5
To use only static methods increases complexity of your code (because you need more parameters for function calls). In this review I won't change this to do not go to far away from your original code but you should also give it a try (for more complex code you will see a huge difference.)
First of all let's move algorithm to a separate class:
static class ...
5
Don't repeat yourself
You use x/size and x%size a lot. You can easily assign them to local variables, and your code becomes much better readable. x is not the best name for an index, consider using i.
int x = i % size;
int y = i / size;
if(x == size-1 && magicNumber-row_sum[y] <= squareSize &&
usedNumbers[...
4
There could be smarter ways to write your code in such a way that it would scale better (for instance, if you were to consider squares of side 4 or 5, you'd have 16 or 25 nested loops and local variables to handle).
First thing first, let's try to see what can easily be improved in your code.
You are considering all matrices of the following form :
a b c
...
4
creating a lot of objects
You are creating a new object every time you branch:
List<SudokuBoard> results = new SudokuBacktrackSolver().solve(newInput);
With a small modification you can use the same object
and avoid a lot of heap allocations.
Here is some pseudo-code:
List<SudokuBoard> solve(SudokuBoard input) {
List<SudokuBoard> ...
4
is_diff_one()
You have chosen to require both strings to be the same length. That's fine, but perhaps you would like to also consider adding or removing one letter to be a difference of one.
A simpler way to write this function would be
def is_diff_one(str1, str2):
return 1 == sum(c1 != c2 for c1, c2 in zip(str1, str2))
The drawback is that it won't ...
4
I'm going to focus on implementing the recursion.
First, let's avoid the globals. The easiest way is to keep the same structure, but move it into a local namespace:
def transform(english_words, start, end):
potential_ans = [start]
results = []
def recursion(start_, end_):
if start_ == end_:
results.append(list(potential_ans))...
4
Broken sort
When inserting elements into your list in sorted order, you don't insert the element at the correct index:
for( int i = 0; i < AMOUNT_OF_TILES_TO_TRY; ++i )
{
if( CURRENT_LENGTH < tilesToTryLengths.get( i ).intValue() )
{
if( i > 0 )
{
tilesToTry....
4
Extraneous loop = massive waste of time
This loop in go_through_board():
for ( int j = col + 1; j <= col_size; ++j )
is not necessary and in fact wastes a lot of time. You only have to work on col + 1, not every column. Once j becomes col + 2, all further computation at that point is wasted because you have skipped column col + 1 (you didn't ...
4
Avoid typedefs that obfuscate the underlying type
These typedefs
typedef long long num;
typedef std::map<char, num> unicorns_t;
make it actually harder hard to read and understand the code. At least give them understandable names if you think these are necessary:
typedef long long longnum; // or largenum
typedef std::map<char, num> ...
4
PEP 8
There is a generally accepted style for Python known as PEP 8. Most notably camelCase functions/methods should become snake_case. There are some other issues with stylistic conventions, I would give the document I linked to an overview.
Main Function
I would advise you add a main function to your program. The main reason being: If I want to use the ...
Only top voted, non community-wiki answers of a minimum length are eligible
