Serac
A menacing post slithers
Let us solve, discuss and share solutions to problems from the glorious site https://projecteuler.net/.
Scan through the problems, notice the common themes (prime numbers, for example), write a library with solutions for those, then call the library to quickly solve each problem.Let us solve, discuss and share solutions to problems from the glorious site https://projecteuler.net/.
Are you sure this is this small ? I have imagining to make several arrays and make specialised algorithms. How is that this is so easy with a map ?This one is trivial, a simple brute force solution is enough. Here is mine: https://pastebin.com/W8qveutv . No surprises, read all numbers into a list, and accumulated the values (max(left_path, right_path) for number at the top)
The other one is more challenging: https://projecteuler.net/problem=67, gonna think about it tonight.
Are you sure this is this small ? I have imagining to make several arrays and make specialised algorithms. How is that this is so easy with a map ?
Sent from my SM-J730GM using Tapatalk
3
7 4
2 4 6
8 5 9 3
[3,7,4,2,4,6,8,5,9,3]
Holy fuck, I found this humongously difficult because of lack of knowledge of several python functions. Feel like a total noob nowNot sure if I understood your reply...
The answer is correct (it was accepted by the site).
You could use a multidimensional array, but it unnecessary. Take the sample output:
It becomes the following list:Code:3 7 4 2 4 6 8 5 9 3
Knowing the row (starting from 0) you are in and your current index (i) in the list, your child indexes are: i + row + 1 and i + row + 2.Code:[3,7,4,2,4,6,8,5,9,3]
Take the number (4) in the third row (row=2), then i=4. And the left child is at position=4+2=1=6 (the number eight in the fourth row).
___
Like I said this is the trivial solution (brute-force all paths and choose the best), the other problem (Maximum path sum II) is more challenging because this trivial program won't work as said in the problem definition.
Oh, I guess the input reading was quite weird. I apologize for thatHoly fuck, I found this humongously difficult because of lack of knowledge of several python functions. Feel like a total noob now
Sent from my SM-J730GM using Tapatalk
from sys import stdin
tokens = map(int, stdin.read().split())
last_row = next(tokens)
numbers = list(tokens)
$ python3 p18-max-path-sum-I.py < input.txt
15
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
It's hardly been a month I've started python. Do you mind explaining me in detail.? Sorry to bother youOh, I guess the input reading was quite weird. I apologize for that
The above code reads from STDIN until end-of-file, it also ignores newline characters and cast every read string to an integer. So it's pretty much: Gimme the triangle row count (the first read number) and all remaning numbers as a 1-dimensional list.Code:from sys import stdin tokens = map(int, stdin.read().split()) last_row = next(tokens) numbers = list(tokens)
So it's meant to be executed like:
Where input.txt is:Code:$ python3 p18-max-path-sum-I.py < input.txt
The first-line is the total triangle height / row count (in this case 15 lines).Code:15 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 17 78 39 68 17 57 91 71 52 38 17 14 91 43 58 50 27 29 48 63 66 04 68 89 53 67 30 73 16 69 87 40 31 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
But the meat of the solution is pretty much standard "pseudo code".
def main():
last_row = 15
numbers = [75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 4, 82, 47, 65, 19, 1, 23, 75, 3, 34, 88, 2, 77, 73, 7, 63, 67, 99, 65, 4, 28, 6, 16, 70, 92, 41, 41, 26, 56, 83, 40, 80, 70, 33, 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
print('Total rows:', last_row)
def path_sum(i, row, acc):
if row == last_row - 1:
return numbers[i] + acc
v = numbers[i]
left_child_index = i + row + 1
sum_left = path_sum(left_child_index, row + 1, v + acc)
sum_right = path_sum(left_child_index + 1, row + 1, v + acc)
return max(sum_left, sum_right)
print('answer=%d' % path_sum(0, 0, 0))
main()
You need to use enumerate/range to get the "'i" going. Or else it's gonna fail I think because it's getting init as 0 and not moving aheadIt's no bother, but explain in detail what? The used python built-ins? How to read input?
Or the whole solution?
If it's about the solution, you can forget about reading input. And hard-code the input values:
Code:def main(): last_row = 15 numbers = [75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 4, 82, 47, 65, 19, 1, 23, 75, 3, 34, 88, 2, 77, 73, 7, 63, 67, 99, 65, 4, 28, 6, 16, 70, 92, 41, 41, 26, 56, 83, 40, 80, 70, 33, 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23] print('Total rows:', last_row) def path_sum(i, row, acc): if row == last_row - 1: return numbers[i] + acc v = numbers[i] left_child_index = i + row + 1 sum_left = path_sum(left_child_index, row + 1, v + acc) sum_right = path_sum(left_child_index + 1, row + 1, v + acc) return max(sum_left, sum_right) print('answer=%d' % path_sum(0, 0, 0)) main()
You need to use enumerate/range to get the "'i" going. Or else it's gonna fail I think because it's getting init as 0 and not moving ahead
Sent from my SM-J730GM using Tapatalk
# Here, path_sum is called twice. With different "i" parameters
# The signature path_sum(i, row, acc)
sum_left = path_sum(left_child_index, row + 1, v + acc)
sum_right = path_sum(left_child_index + 1, row + 1, v + acc)
def main():
last_row = 15
numbers = [75, 95, 64, 17, 47, 82, 18, 35, 87, 10, 20, 4, 82, 47, 65, 19, 1, 23, 75, 3, 34, 88, 2, 77, 73, 7, 63, 67, 99, 65, 4, 28, 6, 16, 70, 92, 41, 41, 26, 56, 83, 40, 80, 70, 33, 41, 48, 72, 33, 47, 32, 37, 16, 94, 29, 53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14, 70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57, 91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48, 63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31, 4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
print('Total rows:', last_row)
def path_sum(i, row, acc):
print(i, row, acc)
if row == last_row - 1:
return numbers[i] + acc
v = numbers[i]
left_child_index = i + row + 1
sum_left = path_sum(left_child_index, row + 1, v + acc)
sum_right = path_sum(left_child_index + 1, row + 1, v + acc)
return max(sum_left, sum_right)
print('answer=%d' % path_sum(0, 0, 0))
main()
(0, 0, 0)
(1, 1, 75)
(3, 2, 170)
(6, 3, 187)
(10, 4, 205)
(15, 5, 225)
(21, 6, 244)
(28, 7, 332)
(36, 8, 431)
...
It ain't that simple, my friend. It's certainly handy to write some general functions (e.g. a prime sieve), but the problems are for the most part highly unique and require quite some ingenuity to solve – every single one of them.Scan through the problems, notice the common themes (prime numbers, for example), write a library with solutions for those, then call the library to quickly solve each problem.
That's not what I noticed when I did some number of them years ago. The problems were Math heavy and soon began lookng the same.It ain't that simple, my friend. It's certainly handy to write some general functions (e.g. a prime sieve), but the problems are for the most part highly unique and require quite some ingenuity to solve – every single one of them.
def read_input():
line_count = int(input())
numbers = []
for _ in range(line_count):
numbers.append(list(map(lambda x: int(x), input().split())))
return line_count, numbers
def main():
row_count, numbers = read_input()
for i in reversed(range(row_count - 1)):
for j in range(i+1):
left_child = numbers[i+1][j]
right_child = numbers[i+1][j+1]
numbers[i][j] += max(left_child, right_child)
print(numbers[0][0])
main()
yup, that's pretty much the solution. My implementation in R I did a while back:https://pastebin.com/m4Kyb646I thought about problem 67: https://projecteuler.net/problem=67.
I lost a lot of time thinking (like 2 hours or so) I had to do something smart (dunno like a magic matrix multiplication or some closed-formula solution), but it was as simple as starting from bottom to top. My first solution (for problem 18) was going from top of triangle to bottom (So 2ˆn comparisons where n is the row count). So I guess the "clever trick" said in the problem definition was going reverse way: I started from second last line in the numbers triangle, and it was enough. (So about nˆ2 comparisons
this time)
Code:def read_input(): line_count = int(input()) numbers = [] for _ in range(line_count): numbers.append(list(map(lambda x: int(x), input().split()))) return line_count, numbers def main(): row_count, numbers = read_input() for i in reversed(range(row_count - 1)): for j in range(i+1): left_child = numbers[i+1][j] right_child = numbers[i+1][j+1] numbers[i][j] += max(left_child, right_child) print(numbers[0][0]) main()
___
I guess problem 68 looks more interesting (It has pictures!): https://projecteuler.net/problem=68
Gonna think about it tonight.
If I understood the problem correctly, it's quite disappointing since the pictures are pretty much irrelevant. (I wanted something visual / geometric!)yup, that's pretty much the solution. My implementation in R I did a while back:https://pastebin.com/m4Kyb646
What's your thoughts on 68?
As with any language, you start by learning its syntax, operators, data structures, primitive types, and built-in utilities. Then it's a matter of becoming comfortable with using all that stuff by solving problems – e.g. the ones at project eulerHey Experts,
Can you map out a way for me to be good at python ?
Sent from my SM-J730GM using Tapatalk
Hardly been a month by now. Im kinda okay with the basics except recursion which seems to mess with my head a lot. I'm giving up on math-ing temporarily, will concentrate more on network programmingAs with any language, you start by learning its syntax, operators, data structures, primitive types, and built-in utilities. Then it's a matter of becoming comfortable with using all that stuff by solving problems – e.g. the ones at project euler
As a tool python is quite flexible. Depends on your goal.Hey Experts,
Can you map out a way for me to be good at python ?
Sent from my SM-J730GM using Tapatalk