• OK, it's on.
  • Please note that many, many Email Addresses used for spam, are not accepted at registration. Select a respectable Free email.
  • See https://www.intpforum.com/threads/incident-of-2018-08-13.27381/

Project Euler

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#3
Lets try doing Maximum route sum.


I'll post my analysis tonight. Use any programming language but let's try doing it without a Tree module as present in java, python, etc

Sent from my SM-J730GM using Tapatalk
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#5
Yeah, post your algorithms within a day or two

Sent from my SM-J730GM using Tapatalk
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#6
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.
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#7
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
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#8
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

Not 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:

Code:
3
7 4
2 4 6
8 5 9 3
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.

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.
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#9
Not 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:

Code:
3
7 4
2 4 6
8 5 9 3
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.

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.
Holy 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
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#10
Holy 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
Oh, I guess the input reading was quite weird. I apologize for that

Code:
    from sys import stdin
    tokens = map(int, stdin.read().split())
    last_row = next(tokens)
    numbers = list(tokens)
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.

So it's meant to be executed like:
Code:
$ python3 p18-max-path-sum-I.py < input.txt
Where input.txt is:
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
The first-line is the total triangle height / row count (in this case 15 lines).

But the meat of the solution is pretty much standard "pseudo code".
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#11
Oh, I guess the input reading was quite weird. I apologize for that

Code:
    from sys import stdin
    tokens = map(int, stdin.read().split())
    last_row = next(tokens)
    numbers = list(tokens)
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.

So it's meant to be executed like:
Code:
$ python3 p18-max-path-sum-I.py < input.txt
Where input.txt is:
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
The first-line is the total triangle height / row count (in this case 15 lines).

But the meat of the solution is pretty much standard "pseudo code".
It's hardly been a month I've started python. Do you mind explaining me in detail.? Sorry to bother you :)


Sent from my SM-J730GM using Tapatalk
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#12
It'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()
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#13
It'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
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#14
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

Hmm, save the file and execute it, there's no problem (I am using Python 3). And the output answer is correct.
___

The "i" is "moving ahead" and there's no need use a range or a for-loop or anything like that. because path_sum is a recursive function. The "i" is one of the function parameters.

Code:
# 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)

Just print the 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):
        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()


The output is (i= 0 then 1 then 3 then 6 then 10 then 15 , etc)

Code:
(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)
...
 

Serac

Prolific Member
Local time
Today, 07:29
Joined
Jun 7, 2017
Messages
1,424
Location
Stockholm
#15
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.
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.
 

baccheion

Active Member
Local time
Today, 02:29
Joined
May 2, 2016
Messages
203
#16
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.
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.
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#17
After fretting over that maximum path sum I realised I need to practice dynamic programming

Sent from my SM-J730GM using Tapatalk
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#18
I 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.
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#19

Serac

Prolific Member
Local time
Today, 07:29
Joined
Jun 7, 2017
Messages
1,424
Location
Stockholm
#20
I 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 &quot;clever trick&quot; 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.
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?
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#21
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?
If I understood the problem correctly, it's quite disappointing since the pictures are pretty much irrelevant. (I wanted something visual / geometric!)

Simplest solution is: brute-force all 10! (less than 4m) permutations. Which is easy for a modern computer (not surprising since the problem is really old).

With a simple insight you can reduce the search-space to 9! (less than 400k). If you toy with the 5-gon you can reduce the search-space further.

The insight is: How can you get a 16-digit string in the 5-gon?

Not sure if my thought process is right, but since this is one of the easier problems (as per the site about section: Generally problems with index < 100 are easier), I guess it is. I did not code the solution yet. Maybe I'll do it later today or tomorrow.

Even though problem 68 looks boring, if we make it more generic we have a hard question to answer:

Given N, a natural number and a list of numbers, how many different totals exist for the magic N-gon? Is it infinite? (I guess not)

___

Currently, I am thinking about problem https://projecteuler.net/problem=459 which is way more fun.
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#22
Hey Experts,

Can you map out a way for me to be good at python ?

Sent from my SM-J730GM using Tapatalk
 

Serac

Prolific Member
Local time
Today, 07:29
Joined
Jun 7, 2017
Messages
1,424
Location
Stockholm
#23
Hey Experts,

Can you map out a way for me to be good at python ?

Sent from my SM-J730GM using Tapatalk
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 euler
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#24
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 euler
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 programming

Sent from my SM-J730GM using Tapatalk
 

Adamastor

Active Member
Local time
Today, 03:29
Joined
May 22, 2009
Messages
145
Location
Brazil, São Paulo
#25
Hey Experts,

Can you map out a way for me to be good at python ?

Sent from my SM-J730GM using Tapatalk
As a tool python is quite flexible. Depends on your goal.
If you wanna learn syntax I recommend doing a simple web-project or some programming challenges to get comfortable with its types and built-in libraries.

For problem solving:
I recommend CodeForces and CS academy you'll learn to use lots of useful python libraries for quick and dirty solutions: collections: deque, defaultdict and itertools, learning how to read input efficiently, etc.

http://codeforces.com/ ---> For fun
https://csacademy.com/ ---> For learning (do everything in-browser)


Python isn't a good language for programming competitions tho (The environment is restricted and generally doesn't have goodies such as numpy; Plus in university and highschool competitions it isn't allowed). If you are serious about it, then learn C++.
 

BurnedOut

Active Member
Local time
Today, 11:59
Joined
Apr 19, 2016
Messages
276
#26
I'm trying hard to not be a script-kiddie. Really. Thanks for your advice !

Sent from my SM-J730GM using Tapatalk
 
Top Bottom