How can I improve my code for euler 14?

2024/4/15 2:14:54

I solved Euler problem 14 but the program I used is very slow. I had a look at what the others did and they all came up with elegant solutions. I tried to understand their code without much success.

Here is my code (the function to determine the length of the Collatz chain

def collatz(n):
a=1
while n!=1:if n%2==0:n=n/2else:n=3*n+1a+=1
return a

Then I used brute force. It is slow and I know it is weak. Could someone tell me why my code is weak and how I can improve my code in plain English. Bear in mind that I am a beginner, my programming skills are basic.

Answer

Rather than computing every possible chain from the start to the end, you can keep a cache of chain starts and their resulting length. For example, for the chain

13 40  20  10  5  16  8  4  2  1

you could remember the following:

  1. The Collatz chain that starts with 13 has length 10
  2. The Collatz chain that starts with 40 has length 9
  3. The Collatz chain starting with 20 has length 8

... and so on.

We can then use this saved information to stop computing a chain as soon as we encounter a number which is already in our cache.

Implementation

Use dictionaries in Python to associate starting numbers with their chain length:

chain_sizes = {}
chain_sizes[13] = 10
chain_sizes[40] = 9
chain_sizes[40]   # => 9
20 in chain_sizes # => False

Now you just have to adapt your algorithm to make use of this dictionary (filling it with values as well as looking up intermediate numbers).

By the way, this can be expressed very nicely using recursion. The chain sizes that can occur here will not overflow the stack :)

https://en.xdnf.cn/q/72970.html

Related Q&A

Visual Studio Code not recognizing Python import and functions

What do the squiggly lines represent in the image? The actual error the flags up when I hover my mouse over the squiggly line is: Import "pyspark.sql.functions" could not be resolvedPylance …

Pandas interpolate() backwards in dataframe

Going forward, interpolate works great:name days 0 a NaN 1 a NaN 2 a 2 3 a 3 4 a NaN 5 a NaN records.loc[:, days].interpolate(…

PEP8 for long methods name [duplicate]

This question already has an answer here:How to choose proper variable names for long names in python(1 answer)Closed 5 years ago.What is the PEP8 correct way for long methods name? I have a unit test…

POST method to upload file with json object in python flask app

I am stuck in a problem where I am trying to build single API which will upload file along with json object. I need this API to create webhook.Using multi part, I am able to upload file and in option f…

Django Logging with FileHandler not Working

I am using the logging setup below with a django project (also using sentry/raven). The sentry/raven bit is working fine, but the file logging isnt. An empty logfile is created, but whenever I use logg…

How to directly access a resource in a Py2app (or Py2exe) program?

This is mostly for Py2app, but I plan to also port to Windows so Py2exe is also applicable.For Mac: How can I access the Resources folder of my app bundle from Python code? The ideal way for me would …

Workflow for Python with Docker + IDE for non-web applications

I am currently trying to insert Docker in my Python development workflow of non-web applications.What are the current best practices in Python development using Docker and an IDE? I need the possibili…

Django Deserialization Error Problem installing Fixture

Traceback (most recent call last):File "/Users/sparshkedia/Desktop/task/venv/lib/python3.6/site-packages/django/core/serializers/json.py", line 69, in Deserializeryield from PythonDeserialize…

Python HTTP Exception Handling

Im running a program that downloads files from a web sit. Ive introduced one exception handling urllib.error.HTTPError, but now Im getting from time to time additional errors that Im not sure how to ca…

Weird lambda behaviour in loops [duplicate]

This question already has answers here:What do lambda function closures capture?(8 answers)Closed 10 years ago.I stumbled upon a behaviour in python that I have a hard time understanding. This is the…