ProjectEuler Problem 719 (some hints, but no spoilers)

-
Last time that I solved a ProjectEuler (PE) problem was in 2015...

This is their latest problem as of today: https://projecteuler.net/problem=719

Number Splitting

      

Problem 719

We define an S-number to be a natural number, n, that is a perfect square and its square root can be obtained by splitting the decimal representation of n into 2 or more numbers then adding the numbers.

For example, 81 is an S-number because 81=8+1.
6724 is an S-number: 6724=6+72+4.
8281 is an S-number: 8281=8+2+81=82+8+1.
9801 is an S-number: 9801=98+0+1.

Further we define T(N) to be the sum of all S numbers n≤N. You are given T(104)=41333.

Find 

The rules of PE prevent me from disclosing the solution (they are very picky about it, rightfully so), but I can chat about the overall idea: 

First, understand that you're dealing with square root, and that the problem is asking for the solution for N=10^12. Use these two data points to understand a bit of the complexity that you want to achieve (don't try O(N), won't work). 

Second, think about how to write some code to, as quick as you can, check whether a number is an S-number. It won't be constant, but the numbers won't be that big either, and the complexity should be a polynomial of Log(number). Think recursively here to solve it. Think pruning the search for a solution (this function has to be fast, as fast as possible). 

Finally, please use long, not int.

When you put it all together, you should test against N=10^4 to make sure you're not going to be off by one or so (there are some weird cases when the numbers are small). Then, run against 10^12. It won't be instantaneous, but it should finish within 5min. In my case, it ran in about 90 seconds:

Running time: 00:01:25.1470336

Unfortunately, for the first time in this blog, no code to be shown since I want to respect the rules of engagement stipulated by PE. But I hope that the idea above gives you some direction. Cheers, ACC.


Comments

Post a Comment

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

-
Image
To solve this Advent of Code (parts 1 and 2), I used Breadth-First Search (BFS) to keep moving the guard as well as Finite State Machine (FSM) to control the directions. This solves part 1 easily. Part 2 can be solved using the same technique, takes a little longer since you need to try every empty cell, but it eventually does the trick (takes a min or so). Code is down below, cheers, ACC. Day 6 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); List map = new List (); int startRow = 0; int startCol = 0; while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); map.Add(new StringBuilder(line)); int indexStart = line.IndexOf('^'); ...
Read more

Golang vs. C#: performance characteristics (simple case study)

-
Image
This is an interesting example to study the performance characteristics of Golang compared to C# for a very particular case (not generalized though).  The same code was written in C# and Golang (literally translated from one to the other). Below you'll be able to see the source code for both. The problem is a simple post-order DFS in a tree-like graph. The code in C# times out (TLE = Time Limited Exceeded). The code in Golang not only works but beats 100% of the other Golang submissions. Take a look the image below: Some potential reasons for the performance gains from Go in this particular example are: 1. Language and Runtime Differences:    Go is compiled directly to machine code, while C# typically runs on a virtual machine (CLR).    Go has a simpler runtime with less overhead compared to the .NET runtime.    Go's garbage collector is designed for low latency, which can lead to better performance in some scenarios. 2. Data Structures:    G...
Read more

Advent of Code - Day 7, 2024: Backtracking and Eval

-
Image
Problem today requires backtracking and eval (evaluating a mathematical expression in the format of a string). Glad that it used a left-2-right evaluation, makes for an easy parsing and not overly complicated evaluation function. Code is down below for parts 1 and 2. Cheers, ACC. Day 7 - Advent of Code 2024 using System.IO; using System.Collections; using System; using System.Text; using System.Text.RegularExpressions; using System.ComponentModel.DataAnnotations; Process2(); void Process() { string fileName = "input.txt"; long retVal = 0; FileInfo fileInfo = new FileInfo(fileName); StreamReader sr = fileInfo.OpenText(); while (!sr.EndOfStream) { string line = sr.ReadLine().Trim(); string[] parts1 = line.Split(':'); long target = Int64.Parse(parts1[0]); string[] numbers = parts1[1].Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); if (TryAll1(numbers, target, "", 0)) r...
Read more