Project Euler

[Ex-User (14663)]

Let us solve, discuss and share solutions to problems from the glorious site https://projecteuler.net/.

 

[baccheion]

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.

 

[BurnedOut]

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

 

[Adamastor]

This one: Maximum path sum I - https://projecteuler.net/problem=18?

 

[BurnedOut]

Yeah, post your algorithms within a day or two

Sent from my SM-J730GM using Tapatalk

 

[Adamastor]

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]

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]

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:

3
7 4
2 4 6
8 5 9 3

It becomes the following list:

[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]

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:

3
7 4
2 4 6
8 5 9 3

It becomes the following list:

[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]

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

    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:

$ python3 p18-max-path-sum-I.py < input.txt

Where input.txt is:

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]

Oh, I guess the input reading was quite weird. I apologize for that

    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:

$ python3 p18-max-path-sum-I.py < input.txt

Where input.txt is:

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]

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:

Spoiler

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]

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:

Spoiler

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]

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.

Spoiler

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

Spoiler

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)

Spoiler

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

 

[Ex-User (14663)]

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]

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]

After fretting over that maximum path sum I realised I need to practice dynamic programming

Sent from my SM-J730GM using Tapatalk

 

[Adamastor]

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)

Spoiler

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]

Problem 459 - https://projecteuler.net/problem=459

Looks really interesting too, since it's about "perfect playing" a game with simple rules. I like this type of problem.

 

[Ex-User (14663)]

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)

Spoiler

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]

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.

Spoiler

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]

Hey Experts,

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

Sent from my SM-J730GM using Tapatalk

 

[Ex-User (14663)]

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]

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]

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]

I'm trying hard to not be a script-kiddie. Really. Thanks for your advice !

Sent from my SM-J730GM using Tapatalk