If there was anything that really got me into Computer Sciences, it’d have to be problem solving. A good friend of mine tempted me into getting into this field by introducing me to something I’d have never heard of before; Competitive Programming.
Already competitive at heart, I really got into solving problems on sites like Project Euler and Kattis where there’s a leaderboard involved. With a load of variety of problems to tackle, there’s no shortage of things to learn. It was this aspect that was really appealing to me.
Although it may seem biased, here are some of my favorite problems which can all be found on Project Euler.
The Lattice Paths problem is one of the first that stumped me for a bit on Project Euler. This problem is presented as follows; Starting from the top left corner of a square grid, how many paths are there to take assuming you can only move right or downwards?
Although simple for smaller grids for larger ones the problem started to seem intimidating, until the results started to feel familiar. Remembering some math that I was taught in the 420.A0 Computer Sciences program at John Abbott I was able to dedude that this was a combinatorics problem and found the solution.
# The Problem can be found here: projecteuler.net/problem=15
deffactorial(n:int)->int:result:int=1foriinrange(1,n+1):result*=ireturnresultdefncr(n:int,k:int)->int:returnfactorial(n)//(factorial(k)*(factorial(n-k)))print(ncr(40,20))
If interested, you can view an alternate solution on my github.
The Lexicographic permutations problem was an interesting one that had me stuck for awhile, but after originally working out the answer by hand I managed to write a working solution. The problem is presented as follows; Given that a permutation is a set of ordered digits, find the 10^6th permutation of digits 0-9.
As I submitted my answer and dived into the forums on Project Euler to see what other people came up with I was pleasantly surprised that I came up with the same algorithm as one of the more seasoned members on the forum. Since we know n digits can occur n! times we can calculate and subtract the sum of the permutations from the total to slowly build our answer.
If interested, you can view an alternate solution on my github.
The Square root convergents problem asks to solve for the first one thousand fractional representations of the square root of two, and count number of fractions where the numerator of those fractions have more digits than the denomiator.
This problem had a surprisingly easy solution, I was able to gather from the examples given that you could always solve for the next fraction using cross multiplcation. The only thing to note is that you're using enough precision because it's easy for the values to be slightly off.
;; The Problem can be found here: projecteuler.net/problem=57(define(sqrtConvergentsnumnd)(if(=num0)0(if(>(string-length(number->stringn))(string-length(number->stringd)))(+1(sqrtConvergents(-num1)(round(/(*n(+nd))d))(+nd)))(sqrtConvergents(-num1)(round(/(*n(+nd))d))(+nd)))))(sqrtConvergents99875)
If interested, you can view an alternate solution on my github.
The Square root digital expansion problem asks to solve for the digit sum of all irrational square roots of n, where n ranges from 1-100.
This problem was really fun to work out, I had to refresh on some math to work out the algorithm by hand and then translate it into code once I felt comfortable with it.
If interested, you can view an alternate solution on my github.
The Sudoku problem is as the name suggests, Sudoku! Tasked with solving a set of given 9x9 Sudoku grids with one given solution, the problem is asking to take the three top left digits from the solved Sudoku grids and find the sum of those three digit numbers.
To solve this problem I used a recursive algorithm to test all valid options in a grid and backtrack when it wasn't possible to go further, until of course a solution is found.
If interested, you can view an alternate solution on my github.