keon / algorithms Goto Github PK

This repo doesn't seem to be consistent about which version of Python the code is written for.

• Some files use type hints (SyntaxError in Python 2)
• Some files use print statements (SyntaxError in Python 3)
• garage.py has a mix of print statements and print as a function (although Python 2 doesn't treat it as a function)

I guess my question is, which version(s) of Python is this repo supposed to be for?

Importing __future__.print_function and adding brackets to all the print statements is fairly easy, but the type hinting is Python 3 only (although they could be moved to the docstrings for cross-compatibility).

Since we now have tests in most of the algorithms, I think it is a good idea to have a separate test_module.py file in each module. We can move all the tests from one module to it, and any further algorithms must have their tests in this file. It will make the repo easy to manage.
@keon what do you think? I can start working on this.

Hey guys, I was wondering we should put all the algorithms in an algorithm folder or something. I feel like It's getting big with all those new files being added to it. I have to scroll all the way down or up to get to where I want and right now I feel it is a bit disorganized. It would be very easy for readers to just click the algorithm folder and look for the intended algorithms inside it. The extra junk can remain outside. What do you guys think?

The function:

def genprime(k):

works extrem slow! Just for small keys k like 64.

• In addition the function generate_key(k) has a bug because the decryption process only fails.

You find the file here

It seems that codes in this repo are more tutorials than tools. I wonder if there is any plan to convert the codes to efficient python apis?

code location: keon/algorithms/blob/master/sort/merge_sort.py

mistake 1

origion code: line - 30

    # Add the left overs if there's any left to the result
    if left:
        arr.extend(left[left_cursor:])
    if right:
        arr.extend(right[right_cursor:])
    return arr

should be ==>

    # Add the left overs if there's any left to the result
    if left_cursor < len(left)::
        arr.extend(left[left_cursor:])
    if right_cursor < len(right)::
        arr.extend(right[right_cursor:])
    return arr

more pythonic efficient way ,no construct sub array ==>

    # Add the left overs if there's any left to the result
    for i in range(left_cursor,len(left)):
        arr.append(left[i])
    for i in range(right_cursor,len(right)):
        arr.append(right[i])
    return arr

mistake 2

origion code : line - 38

print(merge_sort(array, 0, len(array)-1))
print(array)

should be ==>

print(merge_sort(array))

I know this may not the right place to ask this question but I am working on an Android Studio project and am not very familiar with Travis. All I want is to catch syntax errors and undefined names.

I am asking this questions because the travis for this repo does this nicely. However, I'll be working with Java and was wondering anyone with better understanding could point me in the right direction?

@danghai @keon you guys seem to be familiar with travis.

BTW sorry for asking questions not related to the repo but I have been super busy lately with projects and stuff.

Run the flatten(inputArr, outputArr=None) function in python3.5.
It seams ok when the test case is [2, 1, [3, [4, 5], 6], 7, [8]].
But when using [[3, [4, 5], 6], 7, [8]], function outputs [7, 8] not [3, 4, 5, 6, 7, 8].
That is because not None and not [] will be both True in line 10.
Take a = [[3, [4, 5], 6], 7, [8]] as example, first call flatten(a, None).
It will call flatten([3, [4, 5], 6], []). Run till line 10, not outputArr is True where outputArr is [].
Then outputArr will be assigned a new empty list. So it lose [3, 4, 5, 6] in recursive.
It is fine because the first element is single so not [2] is False in given test case.

Bug can fix in:
if outputArr is None:
or
def flatten(inputArr, outputArr=[]) and delete the if statement.

math/rsa.py sometimes shows up an error which means it still has some bugs. It passed previous tests because the data for rsa test is generated randomly, due which like it fails sometimes. This need to be fixed!
https://travis-ci.org/keon/algorithms/builds/366117956
when I restarted build, the test was passed.

https://github.com/keon/algorithms/blob/master/backtrack/general_solution.md
This file, being a text file and written in Java, doesn't fit with the rest of the repo. @keon Should we remove this?

in the garage problem, when i set the initial = [1,2,3,4,0,5,6] and final = [1,6,0,4,5,3,2] ,in your math, the result is 7. But my math will use only require 5 steps to do it which are
[1, 2, 3, 4, 5, 0, 6]
[1, 2, 0, 4, 5, 3, 6]
[1, 2, 6, 4, 5, 3, 0]
[1, 0, 6, 4, 5, 3, 2]
[1, 6, 0, 4, 5, 3, 2]

As the repo grows rapidly, I believe we need more hands on fixing code and reviewing PR.
I recommend @danghai and @SaadBenn to become our new maintainers since they contributed a lot lately.

What do you guys think?
@goswami-rahul @christianbender

array/merge_intervals.py line 54 show be
print(merge_intervals(given))

tests
If I ran the tests I get this kind of error message:

from search.binary_search import binary_search, binary_search_recur
ImportError: No module named 'search'

or

from array.delete_nth import delete_nth, delete_nth_naive
ImportError: No module named 'array.delete_nth'; 'array' is not a package

copy_random_pointer.py
has badly written description and code. Don't know what this does?
@christianbender @keon

@keon @goswami-rahul

nth_digit.py
In this file is the function find_nth_digit(n)
At the moment I ponder what this function does do?
The explanation of the author helps me not.

Tests: At the moment I wrote tests for the module maths

There can be several approaches to solve a problem- the optimal, suboptimal or the brute force approach.
For an algorithm written in x.py, is it a good option to may be discuss the various approaches (write separate function in the file, for each approach)?, or just post the optimal solution?

The reason I brought this up is because, some algorithms in the repo have the optimal code written, while some do not. If a single solution to a problem is to be posted, then it would be good to stick to the optimal one across all files.

If so, would you accept a QuickHull algorithm for solving hulling problems?

Travis caught many errors during its first build with flake8.
It is requested and advised to not add further algorithms until the current known errors are resolved because otherwise, Travis will always show errors for your PR, even if your changes are correct.
Let's fix those errors first! (check the above link).

Running on python 2.7 on Mac High Sierra I get the following error.

 python skyline.py 
  File "skyline.py", line 10
SyntaxError: Non-ASCII character '\xe2' in file skyline.py on line 11, but no encoding declared; see http://python.org/dev/peps/pep-0263/ for details

Are all of these files Python 3 compatible?
If so, please add a line or two about their compatibility with Python 2/3 on the download page.

Thanks

A quick reminder to the newer collaborators :)
Please avoid directly committing to this repo. It is always a good idea and practice to open a PR for any change ( adding an algorithm or modifing something). In this way, other collaborators can review and suggest changes, which will be more helpful for the repo. This will also let identify errors and avoid merges to the main repo causing errors like this one like this one.
@SaadBenn @danghai @christianbender

The file strip_url_params.py is buggy. Because one times the tests run successful and a other times it fails. I comment out the test for this file.

important: The bug is in the function strip_url_params3 of the file above.

@SaadBenn Can you look in it? The project is from you.

I do not see the priority queue (heap) in repo. I am going to write heap (probably min heap) when you approve.

https://github.com/keon/algorithms/blob/master/tree/bst/delete_node.py

at line 63 and 65 the function deletenode is called.
This method does not exist, maybe a recursive call of delete_node was meant?

It would be better to link the python source code and algorithm title on README.md. If you agree with this, I'm willing to add it and make PR.

There should be a requirements.txt file given the python3 version being used

Not that this is all too important, but given that in a (lesser) sense yours is also a python programming showcase, wouldn't it be desirable to honour pep8 suggestions? For example, to avoid camel case names like isEmpty.

Something like Rosetta Stone for code.

Similar repo in ruby.

the prime_test function returns true for 35, while 35 is not a prime.

On running the code for sample paramters below

Input
12

Output
2, 6.0
2, 2, 3.0
3, 4.0

Expected output
2, 6
2, 2, 3
3, 4

Minimal examples of data structures and algorithms in Python

Despite ending with .py, neither of these files have Python code in them.

• make_sentence.py
• combination_sum.py

This is an extension of issue #264
To prepare for packaging, we need to properly explain how api works in our documentation.

I have error when I try to run test_graph for tarjan. I am not sure about this algorithm.
Hello, @mecforlove . It is very nice when you take a review about it? Thanks

FF
======================================================================
FAIL: test_tarjan_example_1 (test_graph.TestTarjan)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/danghai/algorithms/graph/test_graph.py", line 28, in test_tarjan_example_1
    self.assertEqual(g.sccs, [['F', 'G'], ['H', 'D', 'C'], ['E', 'B', 'A']])
AssertionError: Lists differ: [[F, G], [H, D, C], [B, A, E]] != [['F', 'G'], ['H', 'D', 'C'], ['E', 'B', 'A']]

First differing element 2:
[B, A, E]
['E', 'B', 'A']

- [[F, G], [H, D, C], [B, A, E]]
+ [['F', 'G'], ['H', 'D', 'C'], ['E', 'B', 'A']]

======================================================================
FAIL: test_tarjan_example_2 (test_graph.TestTarjan)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/danghai/algorithms/graph/test_graph.py", line 44, in test_tarjan_example_2
    self.assertEqual(g.sccs, [['B', 'E', 'A'], ['D', 'C'], ['G', 'F'], ['H']])
AssertionError: Lists differ: [[E, A, B], [D, C], [F, G], [H]] != [['B', 'E', 'A'], ['D', 'C'], ['G', 'F'], ['H']]

First differing element 0:
[E, A, B]
['B', 'E', 'A']

- [[E, A, B], [D, C], [F, G], [H]]
+ [['B', 'E', 'A'], ['D', 'C'], ['G', 'F'], ['H']]

----------------------------------------------------------------------
Ran 2 tests in 0.002s

FAILED (failures=2)

How is type of license for this project?

It failes for cases

• when beginword and emdword is same
• or differ by 1 letter and both not in wordlist

1. Flip Bit to win: You have an integer and you can flip exactly one bit from a 0 to 1. Write code to find the length of the longest sequence of 1s you could create.
   For example:
   Input: 1775 ( or: 11011101111)
   Output: 8

2. Conversion: Write a function to determine the number of bits you would need to flip to convert integer A to integer B.
   For example:
   Input: 29 (or: 11101), 15 (or: 01111)
   Output: 2

I want to add some additional matrix algorithms and some tests for that.

So, do you have a testing plan of test format, rules of in/output example data, test script name and others?

Not sure how to write unittest to test these function and class in Tree.
My idea is to convert tree to list by pre-order, in-order, post-order traversal and then using assert?

Not sure if this was intended, but the code doesn't seem to access the first all_perms function.