thealgorithms / scala Goto Github PK

View Code? Open in Web Editor NEW

1.1K 71.0 378.0 280 KB

All Algorithms implemented in Scala

License: MIT License

Scala 100.00%

algorithms dsa datastructures education educational scala hacktoberfest

scala's Introduction

The Algorithms - Scala

All algorithms implemented in Scala - for education

Implementations are for learning purposes only. As they may be less efficient than the implementations in the Scala standard library, use them at your discretion.

Getting Started

Read through our Contribution Guidelines before you contribute.

Community Channels

We're on Discord and Gitter! Community channels are great for you to ask questions and get help. Please join us!

List of Algorithms

See our directory for easier navigation and better overview of the project.

How to use this repository for learning purpose ?

Download and install Scala
Clone the repository on your local machine

git clone https://github.com/TheAlgorithms/Scala.git
Open the repository using an IDE (Preferably IntelliJ Idea)
Enable auto-import to import the dependencies from build.sbt
Open the src/main/scala to view the algorithm implementations under various categories
Open src/test/scala to run the test cases and view the algorithm in action
Visit Algorithms-Explained to get a more detailed explanation about specific algorithms
Check Algorithms Visualization for visualization of numerous algorithms

scala's People

Contributors

Stargazers

Watchers

Forkers

sanketvega hayatou wallaceliu ngbountos parameshnalla caojianfa nirbhay-webdev miraai fengyunlzl lingya theborrisz frommymind vinodponna hdbandit bharatnkumar fredc0088 vishnuravi3186 swaraj atifs andreicioban srishti-jain alyswidan sake92 muamba beastneedsmoretorque bogdanmaneam phillip055 bayalla osety commanderasdasd buhijs joyoyoyoyoyo shibu-mahapatra korterling dongdongduang githubxiao037 franksoong gaurav726 kinglai amorskoy devenlu rodrigoberlochi gavinyanyafeng swomack fei115 imran273 swachalit cshaoping st-fresh iamshreeram yan24639916 cypherkaka debanshu23 mng12345 sjl421 ermain-12 abraichdata hariharansrc oneredorange kobataiwan truongle2211 dkaslovsky olexandryermilov mzuehlke romartini33 irishbird cutajarj embarassed liaozhuoran iyounuo ferdib-al-islam orf53975 nkravi atgoud py361 tasselmi rsrinivasan18 ameet20 agustarc fijurrahman rlucas12 xdudandan anticwitee robinofsky hiraitatsuki confidentmachine suaannihilant akpatil zhuohuwu0603 yzism wendaoheri xiejiajun xcresearch carrinayin pradhyu rvojjala plthiyagu roysh gridl pandinosaurus

scala's Issues

Travis CI

Add a .travis.yml file to this repository.
Refer to this doc https://docs.travis-ci.com/user/languages/scala/

Something happened with the Travics CI

Can not build my feature, when i'm read the build details it show me that the sort relevant not build yet and it not even close with what i commit

Functional way to write Sorting algorithm

I can see the imperative code in sorting algorithm, I'm intending to add in functional way
for e.g. In MergeSort , I can see while loop which is an iterative approach -

while (k < high + 1) {
        // must check if empty to avoid exceptions
        if (i > left.length - 1) {
          array(k) = right(j)
          j = j + 1
        } else if (j > right.length - 1) {
          array(k) = left(i)
          i = i + 1
        } else if (left(i) <= right(j)) {
          array(k) = left(i)
          i = i + 1
        } else {
          array(k) = right(j)
          j = j + 1
        }
        k = k + 1
      }

Best Practice: In scala, we follow functional way to write it

def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
    // If either list is empty, return the other list
    case (Nil, _) => ys
    case (_, Nil) => xs
    // If the first element of xs is smaller than the first element of ys,
    // append it to the result of merging the rest of xs with ys
    case (x :: xtail, y :: ytail) =>
      if (x < y) x :: merge(xtail, ys)
      // Otherwise, append the first element of ys to the result of merging xs with the rest of ys
      else y :: merge(xs, ytail)
  }

I'll be creating a PR shortly to add functional code for sorting algorithm given in this repo.

I would want to add a new directory/folder for the problems on Project Euler like Python is having it - https://github.com/TheAlgorithms/Python/tree/master/project_euler.
I will add the code of all the problems I had already solved.

User details

Implementation of Algorithms from CLRS and Art Of Computer Programming

I would like to add Algorithms from CLRS(i.e Introduction to Algorithms, 3rd Edition) as well as from Art of Computer Programming

A series of compilation/test errors in the math algorithms

Error 1

The function abs seems to be not in the global namespace.

[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\main\scala\Mathematics\AbsMax.scala:11:42: not found: value abs
[error]         def absMax(elements : List[Int]): Int = abs(elements.maxBy(x => abs(x)))
[error]                                                 ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\main\scala\Mathematics\AbsMax.scala:11:66: not found: value abs
[error]         def absMax(elements : List[Int]): Int = abs(elements.maxBy(x => abs(x)))
[error]                                                                         ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\main\scala\Mathematics\AbsMax.scala:11:60: diverging implicit expansion for type Ordering[B]
[error] starting with method Tuple9 in object Ordering
[error]         def absMax(elements : List[Int]): Int = abs(elements.maxBy(x => abs(x)))
[error]                                                                   ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\main\scala\Mathematics\AbsMin.scala:11:42: not found: value abs
[error]         def absMin(elements : List[Int]): Int = abs(elements.minBy(x => abs(x)))
[error]                                                 ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\main\scala\Mathematics\AbsMin.scala:11:66: not found: value abs
[error]         def absMin(elements : List[Int]): Int = abs(elements.minBy(x => abs(x)))
[error]                                                                         ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\main\scala\Mathematics\AbsMin.scala:11:60: diverging implicit expansion for type Ordering[B]
[error] starting with method Tuple9 in object Ordering
[error]         def absMin(elements : List[Int]): Int = abs(elements.minBy(x => abs(x)))
[error]                                                                   ^
[error] 6 errors found
[error] (compile:compileIncremental) Compilation failed

This can be fixed by adding import scala.math._, or if you want to use your implementation of abs, use Abs.abs will also work.

Error 2

A right parenthesis is missing in a test case.

[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Array\MaximumAbsoluteDifferenceSpec.scala:9:3: ')' expected but '}' found.
[error]   }
[error]   ^
[error] one error found
[error] (test:compileIncremental) Compilation failed
[error] Total time: 4 s, completed 2020-1-12 22:23:58

This can be fixed by changing assert(MaximumAbsoluteDifferenceSpec.maxAbsDiff(Array(1, 3, -1) === 5) to assert(MaximumAbsoluteDifferenceSpec.maxAbsDiff(Array(1, 3, -1)) === 5) in

Scala/src/test/scala/Array/MaximumAbsoluteDifferenceSpec.scala

Line 8 in 42a0aef

assert(MaximumAbsoluteDifferenceSpec.maxAbsDiff(Array(1, 3, -1) === 5)

Error 3

(folding other similar errors)

[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Sort\SelectionSortSpec.scala:9:49: package Array is not a value
[error]     assert(SelectionSort.selectionSort(arr) === Array(0,1,2,3,7,9))
[error]                                                 ^
[error] 32 errors found
[error] (test:compileIncremental) Compilation failed
[error] Total time: 1 s, completed 2020-1-12 22:29:51

The problem, package Array is not a value, seems to happen because the package name conflicts with the Array scala type, therefore can be fixed with changing package Array to package ArrayTest.

Error 4

[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Array\MaximumAbsoluteDifferenceSpec.scala:8:12: not found: value MaximumAbsoluteDifferenceSpec
[error]     assert(MaximumAbsoluteDifferenceSpec.maxAbsDiff(Array(1, 3, -1)) === 5)
[error]            ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Array\MaximumAbsoluteDifferenceSpec.scala:12:12: not found: value MaximumAbsoluteDifferenceSpec
[error]     assert(MaximumAbsoluteDifferenceSpec.maxAbsDiff(Array(4, 3, 0, 9, -1, 6, -5)) === 17)

I do not know where does the maxAbsDiff comes from. There is not even a method definition. All I can do is to delete that file.

Error 5

[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\AbsMaxSpec.scala:8:33: 6 more arguments than can be applied to method absMax: (elements: List[Int])Int
[error]     assert(AbsMax.absMax(-1000, -1, 999, 72, 65, -56, -767) === 1000)
[error]                                 ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\AbsMaxSpec.scala:12:31: 3 more arguments than can be applied to method absMax: (elements: List[Int])Int
[error]     assert(AbsMax.absMax(121, 221, 3, 4112) === 4112)
[error]                               ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\AbsMinSpec.scala:8:32: 6 more arguments than can be applied to method absMin: (elements: List[Int])Int
[error]     assert(AbsMin.absMin(1000, -1, 999, 72, 65, -56, -767) === 1)
[error]                                ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\AbsMinSpec.scala:12:31: 3 more arguments than can be applied to method absMin: (elements: List[Int])Int
[error]     assert(AbsMin.absMin(121, 221, 3, 4112) === 3)
[error]                               ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\FindMaxSpec.scala:8:35: 6 more arguments than can be applied to method findMax: (elements: List[Int])Int
[error]     assert(FindMax.findMax(-1000, -1, 999, 72, 65, -56, -767) === 999)
[error]                                   ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\FindMaxSpec.scala:12:33: 3 more arguments than can be applied to method findMax: (elements: List[Int])Int
[error]     assert(FindMax.findMax(121, 221, 3, 4112) === 4112)
[error]                                 ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\FindMinSpec.scala:8:35: 6 more arguments than can be applied to method findMin: (elements: List[Int])Int
[error]     assert(FindMin.findMin(-1000, -1, 999, 72, 65, -56, -767) === -1000)
[error]                                   ^
[error] C:\Personal\gitkrakenRepo\Scala-Algorithms\src\test\scala\Mathematics\FindMinSpec.scala:12:33: 3 more arguments than can be applied to method findMin: (elements: List[Int])Int
[error]     assert(FindMin.findMin(121, 221, 3, 4112) === 3)

These failures suggest type mismatch from a List to a series of Numbers, which can be fixed via changing, for example, assert(AbsMax.absMax(-1000, -1, 999, 72, 65, -56, -767) === 1000) to assert(AbsMax.absMax(List(-1000, -1, 999, 72, 65, -56, -767)) === 1000).

Error 6

[info] Mathematics.AbsMaxSpec *** ABORTED ***
[info]   Duplicate test name: should output the correct Integer as a result from the list of elements (AbsMaxSpec.scala:11)
[info] AbsMinSpec:
[info] FindMaxSpec:
[info] FindMinSpec:
[info] AbsSpec:
[info] Run completed in 896 milliseconds.
[info] Total number of tests run: 30
[info] Suites: completed 17, aborted 6
[info] Tests: succeeded 30, failed 0, canceled 0, ignored 0, pending 0
[info] *** 6 SUITES ABORTED ***
[error] Error during tests:
[error]         Mathematics.AbsMaxSpec
[error]         Mathematics.AbsMinSpec
[error]         Mathematics.FindMinSpec
[error]         Mathematics.GreaterCommonDivisorSpec
[error]         Mathematics.FindMaxSpec
[error]         Mathematics.AbsSpec
[error] (test:test) sbt.TestsFailedException: Tests unsuccessful
[error] Total time: 4 s, completed 2020-1-12 22:42:05

Lots of test suites failed. Because their description is duplicated (Duplicate test name). It can be fixed by changing the test names.

Am I missing something in the environment setup? Or is the project just unmaintained and the CI is not running? The second error, missing right parenthesis, does not look like anything that could possibly originate from my flawed environment setup but rather a human error, which should be detected by the CI.

LGTM Analysis error

The LGTM analysis being conducted is treating the code as javascript not scala, anybody know why this is happening?

Dynamic Programming

I would like to be a part in adding few dynamic programming problems like edit distance, knapsack problem, rod cutting problem

Need help on import Scala project with IntellJ

Did anyone met this error when importing Scala project into IntellJ?

[error] sbt.librarymanagement.ResolveException: unresolved dependency: org.apache.logging.log4j#log4j-slf4j-impl;2.8.1: Resolution failed several times for dependency: org.apache.logging.log4j#log4j-slf4j-impl;2.8.1 {compile=[compile(*), master(*)], runtime=[runtime(*)]}::
[error] 	Index 1 out of bounds for length 1
[error] 	Index 1 out of bounds for length 1
[error] 	Index 1 out of bounds for length 1
[error]
[error] 	at sbt.internal.librarymanagement.IvyActions$.resolveAndRetrieve(IvyActions.scala:331)
[error] 	at sbt.internal.librarymanagement.IvyActions$.$anonfun$updateEither$1(IvyActions.scala:205)
[error] 	at sbt.internal.librarymanagement.IvySbt$Module.$anonfun$withModule$1(Ivy.scala:229)
[error] 	at sbt.internal.librarymanagement.IvySbt.$anonfun$withIvy$1(Ivy.scala:190)
[error] 	at sbt.internal.librarymanagement.IvySbt.sbt$internal$librarymanagement$IvySbt$$action$1(Ivy.scala:70)
[error] 	at sbt.internal.librarymanagement.IvySbt$$anon$3.call(Ivy.scala:77)
[error] 	at xsbt.boot.Locks$GlobalLock.withChannel$1(Locks.scala:95)
[error] 	at xsbt.boot.Locks$GlobalLock.xsbt$boot$Locks$GlobalLock$$withChannelRetries$1(Locks.scala:80)
[error] 	at xsbt.boot.Locks$GlobalLock$$anonfun$withFileLock$1.apply(Locks.scala:99)
[error] 	at xsbt.boot.Using$.withResource(Using.scala:10)
[error] 	at xsbt.boot.Using$.apply(Using.scala:9)
[error] 	at xsbt.boot.Locks$GlobalLock.ignoringDeadlockAvoided(Locks.scala:60)
[error] 	at xsbt.boot.Locks$GlobalLock.withLock(Locks.scala:50)
[error] 	at xsbt.boot.Locks$.apply0(Locks.scala:31)
[error] 	at xsbt.boot.Locks$.apply(Locks.scala:28)
[error] 	at sbt.internal.librarymanagement.IvySbt.withDefaultLogger(Ivy.scala:77)
[error] 	at sbt.internal.librarymanagement.IvySbt.withIvy(Ivy.scala:185)
[error] 	at sbt.internal.librarymanagement.IvySbt.withIvy(Ivy.scala:182)
[error] 	at sbt.internal.librarymanagement.IvySbt$Module.withModule(Ivy.scala:228)
[error] 	at sbt.internal.librarymanagement.IvyActions$.updateEither(IvyActions.scala:190)
[error] 	at sbt.librarymanagement.ivy.IvyDependencyResolution.update(IvyDependencyResolution.scala:20)
[error] 	at sbt.librarymanagement.DependencyResolution.update(DependencyResolution.scala:56)
[error] 	at sbt.internal.LibraryManagement$.resolve$1(LibraryManagement.scala:38)
[error] 	at sbt.internal.LibraryManagement$.$anonfun$cachedUpdate$12(LibraryManagement.scala:91)
[error] 	at sbt.util.Tracked$.$anonfun$lastOutput$1(Tracked.scala:68)
[error] 	at sbt.internal.LibraryManagement$.$anonfun$cachedUpdate$19(LibraryManagement.scala:104)
[error] 	at scala.util.control.Exception$Catch.apply(Exception.scala:224)
[error] 	at sbt.internal.LibraryManagement$.$anonfun$cachedUpdate$11(LibraryManagement.scala:104)
[error] 	at sbt.internal.LibraryManagement$.$anonfun$cachedUpdate$11$adapted(LibraryManagement.scala:87)
[error] 	at sbt.util.Tracked$.$anonfun$inputChanged$1(Tracked.scala:149)
[error] 	at sbt.internal.LibraryManagement$.cachedUpdate(LibraryManagement.scala:118)
[error] 	at sbt.Classpaths$.$anonfun$updateTask$5(Defaults.scala:2353)
[error] 	at scala.Function1.$anonfun$compose$1(Function1.scala:44)
[error] 	at sbt.internal.util.$tilde$greater.$anonfun$$u2219$1(TypeFunctions.scala:42)
[error] 	at sbt.std.Transform$$anon$4.work(System.scala:64)
[error] 	at sbt.Execute.$anonfun$submit$2(Execute.scala:257)
[error] 	at sbt.internal.util.ErrorHandling$.wideConvert(ErrorHandling.scala:16)
[error] 	at sbt.Execute.work(Execute.scala:266)
[error] 	at sbt.Execute.$anonfun$submit$1(Execute.scala:257)
[error] 	at sbt.ConcurrentRestrictions$$anon$4.$anonfun$submitValid$1(ConcurrentRestrictions.scala:167)
[error] 	at sbt.CompletionService$$anon$2.call(CompletionService.scala:32)
[error] 	at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
[error] 	at java.base/java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:515)
[error] 	at java.base/java.util.concurrent.FutureTask.run(FutureTask.java:264)
[error] 	at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
[error] 	at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
[error] 	at java.base/java.lang.Thread.run(Thread.java:835)
[error] (*:update) sbt.librarymanagement.ResolveException: unresolved dependency: org.apache.logging.log4j#log4j-slf4j-impl;2.8.1: Resolution failed several times for dependency: org.apache.logging.log4j#log4j-slf4j-impl;2.8.1 {compile=[compile(*), master(*)], runtime=[runtime(*)]}::
[error] 	Index 1 out of bounds for length 1
[error] 	Index 1 out of bounds for length 1
[error] 	Index 1 out of bounds for length 1
Invalid response.

I didn't find any solution in the internet. It is very happy if I can fix this import error. Thank you.