📊Tests and benchmarks
test year_2015::day_01::tests::works_with_samples_v1 ... ok
test year_2015::day_01::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_01 ... ok
year_2015::day_01/year_2015::day_01_v1
time: [6.2931 µs 6.8094 µs 7.3834 µs]
year_2015::day_01/year_2015::day_01_v2
time: [1.9841 µs 1.9896 µs 1.9955 µs]
year_2015::day_01_v1/Naive/7000
time: [63.548 µs 64.204 µs 64.821 µs]
year_2015::day_01_v1/Fast/7000
time: [5.6477 µs 5.8044 µs 6.0121 µs]
Ruby version comments
Ruby's
Stringclass is very well-furnished, even without all of Rail'sActiveSupportgoodness. In that case, just using#count()is enough to get us out of trouble quickly.I am pretty sure there must be an algorithm that doesn't include iterating through the whole string, but so far, the only idea I got would be to use bisecting until I get to the proper index, which just felt like a hassle.
First day wasn't very complicated. I chose to use i16 out of pragmatic reasons, I don't believe Santa would go this high or this low.
I've added a benchmark for this day. The first version had me naively reusing Ruby functionalities, when given Rust's ease of navigating memory, it was faster to just iterate through the data.
There is an EVEN BIGGER optimization that can be done if you treat your string as a bunch of u16 instead of u8.
📊Tests and benchmarks
test year_2015::day_02::tests::works_with_samples_v1 ... ok
test year_2015::day_02::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_02 ... ok
year_2015::day_02/year_2015::day_02_v1
time: [74.835 µs 74.904 µs 74.977 µs]
year_2015::day_02/year_2015::day_02_v2
time: [74.878 µs 74.969 µs 75.067 µs]
Ruby version comments
I..am not even sure this one was complicated in any way.
I used an object-like approach on this one. Using (&self) as he first argument wasn't too much of a stretch since that's exactly how Ruby handles its Object-Oriented pattern in its C code.
I'm not sure yet whether impl FromStr for PresentBox was useful or whether I could have just made my own custom method, but I had fun trying it out. I also like the separation between struct and impl, very neat for converting from/to other C-like languages.
The most annoying part here is dealing with many integers size. Clearly everything here is unsigned, but while I'm sure my box dimensions all fit within u8(0..255), the second I multiply them, I get into u16(0..65_535) range, and when I reach the results, I'm clearly overflowing up to u32(0..4_294_967_295) size. I would love to have each level work nicely with each other, but no, I have to manually cast.
📊Tests and benchmarks
test year_2015::day_03::tests::moves_characters_properly ... ok
test year_2015::day_03::tests::works_with_samples_v1 ... ok
test year_2015::day_03::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_03 ... ok
year_2015::day_03/year_2015::day_03_v1
time: [232.27 µs 232.77 µs 233.35 µs]
year_2015::day_03/year_2015::day_03_v2
time: [250.97 µs 251.71 µs 252.48 µs]
year_2015::day_03_v1/BTreeSet/8192
time: [401.94 µs 402.21 µs 402.50 µs]
year_2015::day_03_v1/HashSet/8192
time: [234.20 µs 234.41 µs 234.64 µs]
year_2015::day_03_v2/BTreeSet/8192
time: [432.48 µs 432.72 µs 432.98 µs]
year_2015::day_03_v2/HashSet/8192
time: [252.37 µs 252.70 µs 253.00 µs]
Ruby version comments
The only thing to be wary of is on line 16: without the call to
#dup, all of Santa's and Robo-Santa's positions will be overwritten, since Ruby's object model has a tendency to pass references when you expect to pass values.Passing by value or reference is a really wonky subject, but this blog post got nice examples that will get you started.
Again, remember to clone your references before modifying, and everything will work out nicely.
This time, the benchmark checks which of BTreeSet or HashSet is faster. Funnily enough, while HashSet is faster at querying elements, it seems BTreeSet is faster at removing them. In our case, we only need to insert, so we can safely go with HashSet.
📊Tests and benchmarks
test year_2015::day_04::tests::works_with_samples_v1 ... ok
test year_2015::day_04::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_04 ... ok
year_2015::day_04/year_2015::day_04_v1
time: [36.404 ms 36.439 ms 36.457 ms]
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 10.6s.
year_2015::day_04/year_2015::day_04_v2
time: [1.0535 s 1.0541 s 1.0545 s]
Ruby version comments
Not gonna lie, brute-forcing MD5 hashes is not something interesting.
Of course, the bastard child had to be annoying, no matter what language we are in. We can actually win A BIT of time here, but we have to fiddle with bytes.
📊Tests and benchmarks
test year_2015::day_05::tests::finds_nice_strings_v1 ... ok
test year_2015::day_05::tests::finds_nice_strings_v2 ... ok
test year_2015::day_05::tests::works_with_samples_v1 ... ok
test year_2015::day_05::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_05 ... ok
year_2015::day_05/year_2015::day_05_v1
time: [51.142 µs 51.447 µs 51.928 µs]
year_2015::day_05/year_2015::day_05_v2
time: [181.19 µs 181.42 µs 181.68 µs]
year_2015::day_05_v1/contains/17000
time: [95.128 µs 95.245 µs 95.361 µs]
year_2015::day_05_v1/chars/17000
time: [50.388 µs 50.474 µs 50.563 µs]
Ruby version comments
Again, Regexp really are one of the best tools in your developer arsenal. In this specific exercise, we can look for repetition by using
\1, which will reference a previously-captured group. Nothing specifically hard beyond that.
Another benchmark, and again it's about the performance of .contains(). Using .try_fold() to return ASAP when any element doesn't satisfy our needs is also a nice touch.
📊Tests and benchmarks
test year_2015::day_06::tests::works_with_samples_v1 ... ok
test year_2015::day_06::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_06 ... ok
year_2015::day_06/year_2015::day_06_v1
time: [13.186 ms 13.320 ms 13.522 ms]
year_2015::day_06/year_2015::day_06_v2
time: [13.437 ms 13.466 ms 13.499 ms]
Ruby version comments
This one actually gave me SOME trouble. My first solution was iterating on each element one by one and was clearly too long. Thankfully, Ruby is really smart when it comes to replacing slices of an array.
There is an even more beautiful solution for part 2 that consist of only tracking the total numbers of flicks on/off/toggle, but in the off chance that a light already off is turned off again, the results would become false.
Also of note: remember what was discussed earlier about references? Well, the documentation covers that too. Quote:
Note that the second argument populates the array with references to the same object. Therefore, it is only recommended in cases when you need to instantiate arrays with natively immutable objects such as Symbols, numbers, true or false.
To create an array with separate objects a block can be passed instead. This method is safe to use with mutable objects such as hashes, strings or other arrays:
I started doing a copy of my original "naive" algorithm, and as it was too slow, I decided to learn how to pass closures in Rust.
📊Tests and benchmarks
test year_2015::day_07::tests::works_with_samples_v1 ... ok
test year_2015::day_07::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_07 ... ok
year_2015::day_07/year_2015::day_07_v1
time: [62.800 µs 62.873 µs 62.940 µs]
year_2015::day_07/year_2015::day_07_v2
time: [127.35 µs 127.56 µs 127.82 µs]
Ruby version comments
We already discovered bitwise operators in the previous exercises, so that shouldn't be too hard. The complication comes from building the wires.
The naive implementation, that works very well with the sample input, consists of interpreting each line one by one, storing the value of each wire every time. Unfortunately, not all inputs are indicated in a linear way.
The answer lies in to store all wires, setting up operations with lazy evaluation, and letting interpretation work itself all the way back.
This one was already complicated in Ruby, but it gets even worse when you have to deal with Rust's lifetimes. The concept in itself is kinda okay to understand, but the way it has to be used sometimes makes no sense. I guess I'll get used to it with time. A nice crate helped me see through it a bit more clearly.
📊Tests and benchmarks
test year_2015::day_08::tests::calculates_length_of_code_strings ... ok
test year_2015::day_08::tests::calculates_length_of_memory_strings ... ok
test year_2015::day_08::tests::calculates_length_of_dumped_strings ... ok
test year_2015::day_08::tests::works_with_samples_v1 ... ok
test year_2015::day_08::tests::works_with_samples_v2 ... ok
year_2015::day_08/year_2015::day_08_v1
time: [13.389 µs 13.434 µs 13.486 µs]
year_2015::day_08/year_2015::day_08_v2
time: [8.7562 µs 8.8298 µs 8.9084 µs]
Ruby version comments
Understanding how characters escaping works is a massive PAIN, and misunderstand the concept is a reason why PHP MySQL injections were so infamous. Things get even more hairy when you have to work with MULTIPLE type of injections (paths, web, sql,...), or even multiple types of string that don't escape the same way,
In that case, we are lucky, since Ruby already implements dump and un-dump, which happens to work exactly as the exercise require. But since we're here to learn, the methods will alternate at runtime between the Ruby methods and the manual implementation.
This one was actually very funny. For a while, I thought it would be a pain to not be able to index strings, but extracting slices actually works better.
📊Tests and benchmarks
test year_2015::day_09::tests::works_with_samples_v1 ... ok
test year_2015::day_09::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_09 ... ok
year_2015::day_09/year_2015::day_09_v1
time: [1.2927 ms 1.2995 ms 1.3064 ms]
year_2015::day_09/year_2015::day_09_v2
time: [4.0988 ms 4.1071 ms 4.1157 ms]
Ruby version comments
Any programming school worth its salt will one day ask of you the shortest path between many points. Often, the idea is that you'll use graph theory and implement Dijkstra's algorithm. Sometimes, the school wants your brain for dinner and you'll be asked to further solve the Traveling Salesman Problem. Both are very interested concepts in themselves, and a good first approach to PathFinding.
If you're not fond of graph transversal, the best answer is often to start using the A* (A-Star) algorithm to iterate through all possible paths.
You can then optimize it, for instance instructing the algorithm to stop searching once it's on a path longer than a previously explored one.
As for finding the "longest path"...just imagine you're not looking for a "shortest" or "longest" path, but a "best" path, and change how that path is selected among others.
This one got me a bit closer to understand how lifetimes function.
While my more experienced counterpart used a cleaner perform-all-permutations approach, I wanted to keep the recursion of my original algorithm, if only to force myself to make lifetimes work across recursion.
📊Tests and benchmarks
test year_2015::day_10::tests::looks_and_says_over_strings ... ok
test year_2015::tests::day_10 ... ok
year_2015::day_10/year_2015::day_10_v1
time: [870.36 µs 872.61 µs 875.35 µs]
year_2015::day_10/year_2015::day_10_v2
time: [12.131 ms 12.153 ms 12.177 ms]
Ruby version comments
This exercise is based on John H. Conway's Look-and-say sequences, you probably know him for the Game of Life, but the mathematician provided us with lot of science.
Nothing really hard in this exercise, except complexity quickly running high, it becomes important to use the best algorithm to generate the next sequence.
Casting between string, chars, bytes,... is slowly becoming more and more natural!
📊Tests and benchmarks
test year_2015::day_11::tests::passwords_are_valid ... ok
test year_2015::day_11::tests::works_with_samples_v1 ... ok
test year_2015::tests::day_11 ... ok
year_2015::day_11/year_2015::day_11_v1
time: [4.8713 ms 4.8800 ms 4.8927 ms]
year_2015::day_11/year_2015::day_11_v2
time: [24.898 ms 24.958 ms 25.035 ms]
Ruby version comments
Another exercise that is actually quite simple when you don't have to account for PERFORMANCE: the complexity in this exercise can quickly become huge and it's important that each of your iterations is as fast as you can. A good tool for that is using Ruby's built-in Benchmark class to compare which of two implementations is the fastest.
Another thing to do is to use heuristics and pre-sanitization: in this exercise, you don't need to iterate and test from
iaaaaaaatoizzzzzzz.
Nothing specific to add on this one. I'm just missing the optimization
📊Tests and benchmarks
test year_2015::day_12::tests::works_with_samples_v1 ... ok
test year_2015::day_12::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_12 ... ok
year_2015::day_12/year_2015::day_12_v1
time: [17.760 µs 17.955 µs 18.183 µs]
year_2015::day_12/year_2015::day_12_v2
time: [30.888 µs 31.305 µs 31.736 µs]
Ruby version comments
That day looked so easy that I could not believe my eyes when I solved it in a simple one-liner:
3.0.0 :001 > pbpaste.scan(/-?\d+/).map(&:to_i).inject(&:+).The second part is a bit more convoluted, but navigating JSON nodes isn't really a pain, you either have a Hash (explore), an Array (explore), or a value (return). Nothing too hard so far.
You know what's faster than using a Regex matcher on a string, or converting it to JSON before traversing it? Iterating though it only once at byte-level.
📊Tests and benchmarks
test year_2015::day_13::tests::parses_input_lines ... ok
test year_2015::day_13::tests::works_with_samples_v1 ... ok
test year_2015::tests::day_13 ... ok
year_2015::day_13/year_2015::day_13_v1
time: [46.791 ms 47.177 ms 47.561 ms]
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 9.9s, or reduce sample count to 50.
year_2015::day_13/year_2015::day_13_v2
time: [86.755 ms 87.306 ms 87.891 ms]
Ruby version comments
Again, refer to Day 09 because we are in a similar configuration, with the exception that we must rejoin our starting point at the end. Nothing too complicated.
Second part is just adding another node with a 0 relationship to all nodes. Surprisingly, it seems our presence lowered the general happiness...
Why do these people even bother having a Christmas dinner together if they hate each other (and us) so much? On the Rust front, beginning to understand ownership a little better, I managed to write this one without resorting to lifetimes. Just makes everything more readable.
Something I also gained over my Ruby implementation is saving a loop: since we are looping back to our initial point at the end of each cycle, a permutation like [0, 1, 2, 3, 4] will have the same value as [1, 2, 3, 4, 0]. Therefore, we only need to generate (brute-force?) sequences starting with our first element. Once we reach our first depth, we can iterate over all available results.
📊Tests and benchmarks
test year_2015::day_14::tests::works_with_samples_v1 ... ok
test year_2015::day_14::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_14 ... ok
year_2015::day_14/year_2015::day_14_v1
time: [3.5302 ms 3.5346 ms 3.5403 ms]
year_2015::day_14/year_2015::day_14_v2
time: [3.5312 ms 3.5359 ms 3.5412 ms]
Ruby version comments
This day doesn't have complicated concepts. If you want to dig, you can think of each reindeer as a finite-state machine, which is one of the concepts that are best solved thanks to Object-oriented programming.
Nothing too different here.
📊Tests and benchmarks
test year_2015::day_15::tests::works_with_samples_v1 ... ok
test year_2015::day_15::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_15 ... ok
year_2015::day_15/year_2015::day_15_v1
time: [35.365 ms 35.613 ms 35.944 ms]
year_2015::day_15/year_2015::day_15_v2
time: [35.463 ms 35.498 ms 35.539 ms]
Ruby version comments
Is there a day where you don't have to iterate through all possible solutions?
I am (partly) joking. I am pretty sure there must be a way to solve n-sided equations, but quite frankly, there's a reason I've always thought of programming as "languages" and not "mathematics". Again, the best thing we can do to avoid an
O(n*n)complexity is finding ways to avoid calculations we know will result in a 0 anywhere.So far, I mainly used loops and other control flow structures, but I decided to go with an
Enumeratorfor this one. No specific change or speedup, but it's the kind of structure we should think of building more often, asEnumerableis the class that made me fall in love with Ruby.
This one was much harder.
After trying many times to use my previous algorithm to mark ranges where numbers were "forbidden", things got heated, and in the end, I reworked something myself by following a proper implementation. However, being in Rust makes the execution of all these loops way faster than it used to be in Ruby.
📊Tests and benchmarks
test year_2015::tests::day_16 ... ok
year_2015::day_16/year_2015::day_16_v1
time: [115.32 µs 115.43 µs 115.53 µs]
year_2015::day_16/year_2015::day_16_v2
time: [81.179 µs 81.202 µs 81.226 µs]
Ruby version comments
See, when I say Ruby's
Enumerableis the perfect, this is the kind of problems I'm talking about.
This one was already easy in Ruby, and it's just as easy in Rust.
📊Tests and benchmarks
test year_2015::day_17::tests::works_with_samples_v1 ... ok
test year_2015::day_17::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_17 ... ok
year_2015::day_17/year_2015::day_17_v1
time: [9.3768 ms 9.3931 ms 9.4143 ms]
year_2015::day_17/year_2015::day_17_v2
time: [9.3911 ms 9.4139 ms 9.4419 ms]
Ruby version comments
Nothing really complicated here, or that we haven't seen yet.
Heh, I'm getting to used to this stuff that it compiled on the second try, and passed the tests on the second. Reworking my Ruby algorithm into Ruby wasn't complicated either.
📊Tests and benchmarks
test year_2015::day_18::tests::works_with_samples_v1 ... ok
test year_2015::day_18::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_18 ... ok
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 5.4s, or reduce sample count to 90.
year_2015::day_18/year_2015::day_18_v1
time: [54.055 ms 54.104 ms 54.155 ms]
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 6.5s, or reduce sample count to 70.
year_2015::day_18/year_2015::day_18_v2
time: [64.643 ms 64.735 ms 64.828 ms]
Ruby version comments
upon Conway's Game of Life earlier, and this exercise is a good example of it.
I thought I was being smart by only keeping track of positions of only ON lights, which was a good implementation for a six-by-six data set, but proved UTTERLY SLOW on the final data set. Using an array of strings (as is the most naive implementation) is indeed the fastest way to do it. I still kept the old code commented.
That was fun.
My distinguished competitor used a single-dimensional vector approach, which may have a better performance, but quite frankly, I prefer having representation closer to "physical" reality. But it's just me, don't listen to me too much.
📊Tests and benchmarks
test year_2015::day_19::tests::works_with_samples_v1 ... ok
test year_2015::day_19::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_19 ... ok
year_2015::day_19/year_2015::day_19_v1
time: [565.05 µs 565.71 µs 566.40 µs]
year_2015::day_19/year_2015::day_19_v2
time: [6.0105 µs 6.0169 µs 6.0237 µs]
Ruby version comments
Part one is nothing to write home about. However, part two... First idea was the good ol' brute-force approach, but when searching if there was an algorithm I didn't know, I stumbled upon a very interesting Reddit comment...
Okay, that was less painful than I remembered it, and my Rust code is actually clearer than my Ruby code.
📊Tests and benchmarks
test year_2015::day_20::tests::works_with_samples_v1 ... ok
test year_2015::tests::day_20 ... ok
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 45.9s, or reduce sample count to 10.
year_2015::day_20/year_2015::day_20_v1
time: [454.92 ms 455.72 ms 456.56 ms]
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 50.1s, or reduce sample count to 10.
year_2015::day_20/year_2015::day_20_v2
time: [497.94 ms 498.66 ms 499.45 ms]
Ruby version comments
I've had to calculate list of primes and divisors in the past, and it always sucked. My previous algorithms were correct but always too long (but what is "long" when you're nearing infinity?).
Again, outside help is a great resource to find algorithms better than yours.
I remembered this one was A PIECE OF SHIT to run in Ruby, as it lasted around over minute on my machine the last time I ran it. Having it run in only one second here is a real pleasure. Some issues flip-flapping between types, but nothing too brutal.
📊Tests and benchmarks
test year_2015::day_21::tests::wins_the_fight_with_samples_v1 ... ok
test year_2015::tests::day_21 ... ok
year_2015::day_21/year_2015::day_21_v1
time: [4.8485 µs 4.8549 µs 4.8618 µs]
year_2015::day_21/year_2015::day_21_v2
time: [4.8473 µs 4.8539 µs 4.8609 µs]
Ruby version comments
...really nothing to say here.
Couldn't believe this one is running so fast.
📊Tests and benchmarks
test year_2015::tests::day_22 ... ok
year_2015::day_22/year_2015::day_22_v1
time: [18.188 ms 18.206 ms 18.225 ms]
year_2015::day_22/year_2015::day_22_v2
time: [29.689 ms 29.734 ms 29.782 ms]
Ruby version comments
"Any sufficiently advanced bruteforce is indistinguishable from Dijkstra's algorithm"
As for this exercise, a key lesson is: make commits BEFORE you rewrite your code. In that occasion, rewriting my code made it unworkable, no matter how many times I tried, and I must have made the same input mistake many times because my second day results were always off by twenty, even when carefully copying an algorithm that works. In the end, it all boiled down to an off-by-one error.
I just hate this one, let's get it over with.
📊Tests and benchmarks
test year_2015::day_23::tests::iterates_over_program ... ok
test year_2015::tests::day_23 ... ok
ar_2015::day_23/year_2015::day_23_v1
time: [6.7568 µs 6.7660 µs 6.7749 µs]
year_2015::day_23/year_2015::day_23_v2
time: [4.8121 µs 4.8186 µs 4.8261 µs]
Ruby version comments
We are not Turing complete yet, but learning to write a virtual machine is always a fun exercise to understand how computers work.
As a small bonus on this exercise, instead of re-interpreting each instruction as they come, which can be costly on the long term, I used an approach similar to Ahead-of-time compilation to have all my instructions in
machine codeRuby code and ready to reuse as needed.That said: make sure you ALWAYS read the exercise WORD. BY. WORD. Because if
jiemeans "jump-if-even", it does not meanjiowill mean "jump-if-odd".
Heh, I love this one, whether it's in Ruby or in Rust.
📊Tests and benchmarks
test year_2015::day_24::tests::works_with_samples_v1 ... ok
test year_2015::day_24::tests::works_with_samples_v2 ... ok
test year_2015::tests::day_24 ... ok
year_2015::day_24/year_2015::day_24_v1
time: [15.294 ms 15.326 ms 15.360 ms]
year_2015::day_24/year_2015::day_24_v2
time: [3.5474 ms 3.5596 ms 3.5719 ms]
Ruby version comments
While this looks like YABA (Yet Another Brute-force Algorithm), Ruby's got a very useful
#combinationmethod that will generate permutations around for you. And of course, knowing when to exit the loop at the best time is half the battle.
Would you believe it? The combinations(n) method also exists in Rust!
📊Tests and benchmarks
test year_2015::day_25::tests::works_with_samples ... ok
test year_2015::tests::day_25 ... ok
year_2015::day_25/year_2015::day_25
time: [148.18 ns 148.33 ns 148.49 ns]
Ruby version comments
You could solve this one by calculating each number one-by-one, cell-by-cell,... Or you could use modular exponentiation.
If you're careful, you will quickly understand that your operation will at some point look like
STARTER * MULT % MODULO * MULT % MODULO etc..., and that once you know how many cells you need to iterate through, you can just repeat the* MULT % MODULOpart.Not being a math nerd at all (I've learned to talk to machines, not to numbers), the subject was completely lost on me, but here is some help: the modulo operation itself is very funny: once you apply it once, you don't need to repeat it, since it would just end up on the same number. So you can just repeat the multiply operation many times (isn't that a "power" operation?) and apply the modulo only once.
How about this:
> 9999 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 * 18 % 7 => 6 > 9999 * 18 * 18 * 18 * 18 * 18 * 18 * 18 * 18 % 7 % 7 % 7 % 7 % 7 % 7 % 7 % 7 => 6 > 9999 * 18 * 18 * 18 * 18 * 18 * 18 * 18 * 18 % 7 => 6 > 9999 * 18**8 % 7 => 6Now, I got it, and so do you. Merry Xmas!
That one was very easy in Rust too, I just had to pick up an algorithm online to properly perform modular exponentiation since it doesn't seem available in Rust.