elmendalerenda / octubre-karate-chop Goto Github PK
View Code? Open in Web Editor NEWThis project forked from 12meses12katas/octubre-karate-chop
Kata del mes de Octubre del 2011: Karate Chop
Home Page: www.12meses12katas.com
This project forked from 12meses12katas/octubre-karate-chop
Kata del mes de Octubre del 2011: Karate Chop
Home Page: www.12meses12katas.com
---- KARATE CHOP ---- (enlace original: http://codekata.pragprog.com/2007/01/kata_two_karate.html) A binary chop (sometimes called the more prosaic binary search) finds the position of value in a sorted array of values. It achieves some efficiency by halving the number of items under consideration each time it probes the values: in the first pass it determines whether the required value is in the top or the bottom half of the list of values. In the second pass in considers only this half, again dividing it in to two. It stops when it finds the value it is looking for, or when it runs out of array to search. Binary searches are a favorite of CS lecturers. This Kata is straightforward. Implement a binary search routine (using the specification below) in the language and technique of your choice. Tomorrow, implement it again, using a totally different technique. Do the same the next day, until you have five totally unique implementations of a binary chop. (For example, one solution might be the traditional iterative approach, one might be recursive, one might use a functional style passing array slices around, and so on). Goals This Kata has three separate goals: As youÕre coding each algorithm, keep a note of the kinds of error you encounter. A binary search is a ripe breeding ground for "off by one" and fencepost errors. As you progress through the week, see if the frequency of these errors decreases (that is, do you learn from experience in one technique when it comes to coding with a different technique?). What can you say about the relative merits of the various techniques youÕve chosen? Which is the most likely to make it in to production code? Which was the most fun to write? Which was the hardest to get working? And for all these questions, ask yourself "why?". ItÕs fairly hard to come up with five unique approaches to a binary chop. How did you go about coming up with approaches four and five? What techniques did you use to fire those "off the wall" neurons? Specification Write a binary chop method that takes an integer search target and a sorted array of integers. It should return the integer index of the target in the array, or -1 if the target is not in the array. The signature will logically be: chop(int, array_of_int) -> int You can assume that the array has less than 100,000 elements. For the purposes of this Kata, time and memory performance are not issues (assuming the chop terminates before you get bored and kill it, and that you have enough RAM to run it). Test Data Here is the Test::Unit code I used when developing my methods. Feel free to add to it. The tests assume that array indices start at zero. YouÕll probably have to do a couple of global search-and-replaces to make this compile in your language of choice (unless your enlightened choice happens to be Ruby). def test_chop assert_equal(-1, chop(3, [])) assert_equal(-1, chop(3, [1])) assert_equal(0, chop(1, [1])) # assert_equal(0, chop(1, [1, 3, 5])) assert_equal(1, chop(3, [1, 3, 5])) assert_equal(2, chop(5, [1, 3, 5])) assert_equal(-1, chop(0, [1, 3, 5])) assert_equal(-1, chop(2, [1, 3, 5])) assert_equal(-1, chop(4, [1, 3, 5])) assert_equal(-1, chop(6, [1, 3, 5])) # assert_equal(0, chop(1, [1, 3, 5, 7])) assert_equal(1, chop(3, [1, 3, 5, 7])) assert_equal(2, chop(5, [1, 3, 5, 7])) assert_equal(3, chop(7, [1, 3, 5, 7])) assert_equal(-1, chop(0, [1, 3, 5, 7])) assert_equal(-1, chop(2, [1, 3, 5, 7])) assert_equal(-1, chop(4, [1, 3, 5, 7])) assert_equal(-1, chop(6, [1, 3, 5, 7])) assert_equal(-1, chop(8, [1, 3, 5, 7])) end
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.