New answers tagged programming-challenge
0
As others have pointed out, if you are brute-forcing this:
there's no reason to keep the old values around in a list. You just need a += b; b += a; to go 2 steps, or in Python a,b = b,a+b to go one step.
binary integer -> base-10 digit string is very expensive, requiring repeated division by 10 or equivalent. (And that's division of the whole BigInteger ...
2
Disclaimer: This is not a proper review. I just want to give a taste of how the Project Euler problems shall be addressed.
Given a number \$x\$, it is triangular if there exist \$n\$ such that
\$\dfrac{n(3n-1)}{2} = x\$
Solving for \$n\$, gives \$n = \dfrac{1 + \sqrt{1 + 24x}}{6}\$
Similarly, for it to be pentagonal, there must be \$k\$ such that
\$\...
1
Let's start with a quick analysis of your current algorithm. For each number less than n (1000000 in your case) it does sqrt(n)log(n) operations (sqrt for is_prime*logcycles). However, some fairly simple things about this problem make it much easier to solve.
As you probably know, any 2 digit or greater number ending in 2,4,6,8 or 5 is not prime since it is ...
2
Instead of generating 3 million numbers and store them in memory, you only need to generate 3 of them at a time (one triangular, one pentagonal and one hexagonal) and compare them. The lowest should be advanced to the next of its kind and the processus repeated. That way you only generate the amount of numbers you need to achieve your goal and you don't put ...
2
The way this was written, it was meant to steer you in the direction you did.
Find the next triangle number that is also pentagonal and hexagonal.
You loop the triangles to find matches in the others:
for triangle in triangles:
if triangle in pentagons and triangle in hexagons:
yield triangle
But if you think about it, there are more ...
0
Rubocop Report
There are a couple of additional offenses against Ruby style guide and conventions that haven't been addressed in the excellent answer.
Use # frozen_string_literal: true top level comment (why?).
Insert an empty line after guard clauses: return false if self < 1.
Prefer the zero predicate over 0 check: self % i == 0 -> (self % i).zero?.
...
2
There's no need to write a max() method. The Standard Library provides for that.
A for comprehension, with a yield clause, produces a result. So instead of using a mutable var to capture and collect the results of the yield you should capture them directly.
val res = for {...} yield {...}
Or, if you want to process the results more directly, i.e. without ...
0
// ********* 338. Counting Bits *********
The previous solution will fail for the input [0].
func countBits(_ num: Int) -> [Int] {
var result = [0]
guard num != 0 else {
return result
}
for i in 1...num {
result.append(result[i/2] + (i % 2))
}
return result
}
1
Code review
The sequence of
if condition:
return True
return False
is a long way to say
return condition
Consider instead
def is_palindrome(n):
return to_str == to_str[::-1]:
Generator vs list.
A list takes space. The entire point of a generator is to not take space. Your find_palindrome does yield, that is produces one ...
0
You know that a prime other than 2 and 5 ends in 1, 3, 7 or 9. What does that tell you about the digits of x if it is right truncatable? It tells you that all the digits after the first must be 1, 3, 7 or 9.
On the other hand, if you have a four digit left-truncatable number, then the last three digits are also left truncatable. So the find the n+1 digit ...
3
The thing about these "story" problems is that the story is often distracting, if not outright misleading, from the underlying problem to be solved.
In this case your code solves the challenge by calculating and counting the number of jumps it takes to get from the beginning to the end. More or less the way the story is layed out. But it's worth noting:
...
2
There is math.factorial function. So no need to reinvent it.
Using try/except for control flow is a bad practice. It's better to explicitly check whether a list contains a value using the condition if int(digit) in factorials. It also will eliminate the code duplication in except branch.
It's even better to pre-calculate all factorials for digits from 0 to 9....
1
Your comprehensions are hard to understand, as you have two on one line. I recomend you spread them over multiple lines to increase readability.
There is no benifit to using a dictionary comprehension, and only makes me think you're abusing comprehensions.
Just use a normal for loop and use yield.
You don't need to pass n, you can find the limit by using ...
3
If I were to compute the answer, I'd do (language shown is JavaScript):
var n = 1e8;
var v = Math.floor(n / 3);
6 has two multiples of three less than or equal to it: 6 / 3 == 2
127 has 42: 127 / 3 == 42.3333, thus Math.floor(127 / 3) == 42.
Likewise, 3 * n will have n multiples of three, including three itself.
0
Your docstring is misleading.
The function does not return a sequence; it returns a generator.
It states “for a and b in range(n)”, which is incorrect. They are in range(2, n+1). If you don’t want to confuse the issue with range() excluding the last value, say “for a and b in the range from 2 to n, inclusive”.
The problem refers to a “sequence”, where the ...
8
If you are insisting on counting, instead of computing the answer, you can optimize your counting loop by just looping over the multiples of 3:
for(int i = 3; i <= x; i += 3) {
count++;
}
8
Use your brain, not brute force. How would you solve the problem if it were presented in a math test, and you couldn't use a computer?
Your solution requires \$O(x)\$ time; it should be possible in \$O(1)\$.
-2
I find this a simpler solution to the problem with shorter code.
const arr = [];
let sum = 0;
for (i = 1; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) {
arr.push(i);
sum = arr.reduce((total, a) => total + a, 0);
}
}
console.log(sum);
1
Inside the inner loop, \$1/k\$ is a constant term. So you could extract that multiplication from the inner loop, and apply it on the computed subtotal. This won't change the order of complexity though.
I was wondering if there is a closed form for computing the sum of reciprocal powers (to replace the summing and thereby speed things up), but I couldn't ...
16
It's possible to calculate the nth Fibonacci number directly thanks to Binet's formula.
Due to floating point errors, the formula doesn't give correct values if n is too large, but it works fine in order to calculate the number of digits.
from math import log10, floor, ceil
def fibonacci_digits(n):
if n < 2:
return 1
ϕ = (1 + 5**0.5) / ...
10
Project Euler has quite a few problems on the Fibonacci numbers. Other things also repeatedly crop up, like prime numbers, triangular numbers, and so on. In fact, quite a few problems build on earlier, easier, problems.
Because of this it is worth it to start designing your functions for reusability. Put these functions into modules, so you can reuse them ...
1
making your code harder to read:
lack of docstrings
lack of comments
unwarranted indentation using an else: after a "disruptive if"
(transferring execution with return, break, continue)
(Here, you are using this with otherwise empty "if-parts":
you could negate the conditions and just use the former else:-statements. Hello again, indentation.)
2
You’re building up a huge list of permutations in order to get to exactly one permutation. This is needlessly using time (computing all permutations that come before it) and memory (storing all those permutations in a list.
If you have 9 objects, you can have 9! = 3,628,800 permutations. So with the 10 digits, 0 through 9, the first 362,880 permutations ...
16
Two comments:
There isn't any reason to keep a list of all the fib numbers. You only need the last two numbers to compute the next one.
A number with 1000 digits satisfies 1e1000 <= f < 1e1001. It might be faster to compare f to the numbers rather than to convert it to a string and get its length.
def fib_of_length(n):
"""returns index of the ...
14
This isn't a full review but something I found very interesting about this problem: I would have thought that keeping a list of every Fibonacci number would get expensive over larger numbers but that doesn't seem to be the case with my testing.
Instead it seems the bottleneck is the line:
len(str(fibs[-1])) < n:
I ran the function for n = 10,000 and it ...
2
itertools.islice()
Looks pretty good, but generating a list of all the permutations can take a lot of memory. Use itertools.islice() to skip over the first 999,999 permutations that you don't want. The indexing parameters to islice are just like for range(start, stop, step)
def lexicographic(n, digits):
"""Assumes digits a string.
returns the nth ...
2
I'd like to advocate for a more functional programming style. We all know object orientation can provide clarity over procedural programming, but if you can replace for loops and if statements with Select and Where? I'd say that's even better.
Here's how:
public static int GetMoneySpent(int budget, int[] keyboards, int[] drives)
{
var ...
5
You were right on track with
no_start = str[1:]
no_end = no_start[:len(no_start) - 1]
In a first step, they can be combined:
return str_[1:len(str_)-1]
Note: I changed str to str_ because str is actually a datatype in Python.
The next thing to know about slicing, is that you can use negative indices to index from the back without specifically using the ...
2
The code looks quite good in general. Without a deeper look at the problem, there are twothree things that can easily be improved:
Building the look-up table
You use
letter_scores = {letter: ord(letter) - 64 for letter in string.ascii_uppercase}
which makes use of the ASCII encoding to determine the value of each letter. The following could be considered ...
1
The code looks quite succinct and sufficient. The only suggestions I would offer are minor tweaks:
for the imperative solution, a for...of loop could be used to eliminate the need to do bookkeeping on the counter variable and use it to index into the string to get each character:
for(const c of s) {
if (par[c]) {
rep.push(par[c]);
} else {
if (...
2
The standardlibrary module math already contains a factorial function. On my machine it is about 20 times faster than your function using n = 100. It also does not suffer from stack size limitations as yours does (try computing fact(3000)).
Alternatively you could learn about memoizing, which will help you in many Project Euler problems. Here it would be ...
2
Solving without Recursion
Here is a very simple way to solve this specific problem without recursion and with only a single function. It might not extend to all the similar problems you want to, but it could extend to some of them:
def letterCasePermutation(S):
results = [S]
for i, char in enumerate(S):
if char.isalpha():
...
1
whole algorithmic change => \$O(n)\$
Your existing algorithm is quite confusing. Perhaps instead you could try a simpler structure such as:
from datetime import date
def num_sundays_on_first_of_month(year1, year2):
num_sundays = 0
for i in range(year1, year2+1):
for j in range(1, 13):
if date(i, j, 1).weekday() == 6:
...
1
Readability / maintainability
def get_sum_amicable(n, divs={2:1}):
"""Yields amicables below n."""
for number1 in range(n):
for number2 in range(number1):
try:
if divs[number2] == number1 and divs[number1] == number2:
yield number1
yield number2
except KeyError:
...
1
It's fairly common to use an auxiliary parameter as an index or accumulator in recursive functions. If you don't like having the extra function or method "cluttering" the namespace, you can nest it inside the driver like this:
class Solution:
def letterCasePermutation(self, S):
def aux(S, i):
if i >= len(S) and len(S) > 0:
...
0
You could use a while loop instead of this:
for(; n1>=100; n2--)
It would look cleaner like this:
while(n1 >= 100) {
// ... some code here
n2--;
}
4
One thing I like about this code is the clear division of role.
You have a section for identifying and extracting the hourglasses. Then you sum the individual hourglasses. Then you find the maximum.
There's a quote by Computer Scientist Tony Hoare that "There are two ways to write code: write code so simple there are obviously no bugs in it, or write ...
1
Performance Problems
Your current solution works decent for small cases, but there are a few problems when the problem starts to scale up, which causes the performance to drop. I will mention the two biggest I have found.
You construct all paths toward the goal, even the unviable ones, in full until you remove them. This causes an exponential amount of ...
2
In terms of the times on LeetCode, they can be dependent upon the server load as much as the code. I tried your code and got a range of times from 100 ms to 136 ms. Holding onto the last node is a better solution than repeatedly trying to find it but on a list of only a few nodes I don't know how much impact it would have.
In terms of the code, this ...
3
I have a few suggestions for you:
You should get in the habit on wrapping all code that isn't in a function in a main guard, to ensure that that code only runs if that file is running, and to protect it from import mishaps
Running your code with pylint, a few warnings that popped up were:
Returns: All return statements should return something or none of ...
1
I combined some of the previous answers, and shortened it up a little
function findShortestWordAmongMixedElements(arr) {
return arr.filter(item => item.constructor === String)
.sort((a, b) => a.length - b.length)[0] || '';
}
1
num_to_alpha =\ is not Pythonic. If a statement is “incomplete”, there is no need to add a trailing \ to indicate the line is continued. An “incomplete” statement is one which contains unclosed {, [, or (, so this line could be written without the trailing \ simply by moving the { up to the previous line:
num_to_alpha = {
1: 'one', ...
The if 0 < ...
6
Solution 1
You have two equations and three unknowns. Since three minus two is one, you should only require one search loop.
a + b + c = 1000
=> c = 1000 - a - b
a2 + b2 = c2
=> a2 + b2 = (1000 - a - b)2
=> a2 + b2 = 10002 - 2000a - 2000b + 2ab + a2 + b2
=> 0 = 1000000 - 2000a - 2000b + 2ab
=> 0 = 500000 - 1000a - 1000b + ab
=> 1000b - ab = 500000 - ...
1
time: O(n)
memory: O(1)
collatz_count()
To start, your collatz_count() function could be simpler and easier to read. The recursion in your collatz_count() function is confusing and too long.
Also, do use integer division (//) to cut down on memory (floats take more space than integers).
def collatz_count(n):
length = 0
while n != 1:
...
8
If you want a solution that doesn't involve any coding, you can use the fact that Pythagorean triples \$a < b < c\$ are of the form
\$a = 2pqr\$
\$b = p(q^2 - r^2)\$
\$c = p(q^2 + r^2)\$
or the same equations with \$a\$ and \$b\$ switched.
Here \$p, q, r\$ are positive integers, which are uniquely determined by the condition
\$p = \gcd(a, b, c)\$....
2
Personally I tend to avoid creating classes, which do not implement any logic. Sometimes it makes sense or is even necessary, but always when I see such a class, I try to find out what operations are performed on its data and if they shouldn't be implemented as methods of that class.
What I don't like about your code is the ProcessCart method, which pretty ...
1
def collatz_count(n, count={1: 1}):
"""uses cache (count) to speed up the search, returns sequence
length for the given number"""
Are you sure it speeds it up? It certainly looks completely useless, because neither the looped top call
[(x, collatz_count(x)) for x in range(1, 1000000)]
nor the recursive calls reuse the cache.
-3
def check_even(num):
if num % 2 == 0:
return True
else:
return False
a = []
b = []
c = 0
for i in range(1000000, 100000, -1):
a = []
c = i
while c != 1:
if check_even(c):
a.append(c)
c = int(c/2)
else:
a.append(c)
c = 3 * c + 1
b.append(len(a))
print(...
2
Your counter is a cumulative sum of elevation changes; elevation would be a more precise name for it.
Ultimately, the goal is to count the number of times the elevation changes from -1 to 0. To do that:
Translate the 'U' and 'D' steps into +1 and -1, respectively.
Obtain a sequence representing the elevation profile of the hike using Seq.scan.
Count the ...
6
Integer Division
In Python, 10 / 2 is equal to 5.0, not 5. Python has the integer division operator (//) which produces an integral value after division, instead of a floating point value. To prevent storing both int and float keys in the count dictionary, you should use:
count[n] = collatz_count(n // 2) + 1
Cache
Your count cache works nicely. ...
Top 50 recent answers are included
