Questions tagged [memoization]

An optimization technique where function calls are cached to avoid duplicate computations.

Filter by
Sorted by
Tagged with
0
votes
1answer
85 views

Python 3 weighted random choice function memoized version

I have written a function that randomly picks one element from a set with different probabilities for each element, anyway it takes a dictionary as argument, the keys of the dictionary are the choices ...
2
votes
1answer
99 views

Longest common subsequence — recursion and memoization

...
8
votes
1answer
295 views

Find all paths in a graph

My code does a DFS on the given graph and prints all possible paths for a given start and end node. My question is how can this be improved? Can some form of memoization be used here? There are cases ...
0
votes
0answers
60 views

Efficiently calculate value of Pascal's Triangle using memoization and recursion(updated)

Follow up to Efficiently calculate value of Pascal's Triangle using memoization and recursion Based on feedback given by jvwh in the answers ...
3
votes
1answer
123 views

Efficiently calculate value of Pascal's Triangle using memoization and recursion

So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
2
votes
1answer
248 views

C++17 Recursive Fibonacci calculation with memoization

Compiler is g++ 4.2. I'm new to C++, but I've done a lot of data science, web scraping, and some socketing stuff in Python. This code generates the nth Fibonacci number, either with a naive ...
1
vote
3answers
110 views

Advent of Code 2020, Day 10 in Ruby

I'm an amateur programmer making a career change into web development. I've found Advent of Code challenges are great way to sharpen my skills. I've cleaned up this solution for Day 10, 2020 as much ...
1
vote
1answer
246 views

Optimizing solution of Sum of Pairs: Codewars in Python

I need help to optimize my code for huge lists with approx. 10000000 elements. Is there a way to improve my algorithm or should I try to build a new one using a completely different approach? Task: ...
1
vote
1answer
85 views

Generic memoize function in Swift

I need to perform some expensive calculation, such as determining a Fibonacci number: ...
6
votes
1answer
110 views

Generic memoize utility function for pure functions

Given the following generic memoize utility for pure functions with type hints: ...
6
votes
1answer
168 views

Memoizing a tree's parent pointers in Python

I have a simple binary tree that has no parent pointers. ...
3
votes
1answer
89 views

Fibonacci Sequence using Recursion with Memoisation

File fibonacci.aec: ...
2
votes
2answers
109 views

Knapsack performance issue

I'm solving a knapsack problem here. It works, but gives time limit exceeds on a certain test case. Problem statement There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of ...
3
votes
0answers
91 views

Unique Distancing Problem, Memoization in Haskell

note: You might be scared seeing the length of the post, but it's actually not that long because you don't need to read the compiler logs or the python code to understand my code (I wish StackExchange ...
3
votes
1answer
57 views

Creating valid words on an n-by-n grid of characters using depth-first search

I am trying to create a word-finder game. There will be an n-by-n Board filled with Tiles. ...
1
vote
0answers
212 views

Extract useMemo to its own custom hook

I wanted to know if the useMemo function extracted like this is valid at all. This is a whole component (Sorry for the imports) that uses useMemo to get a data that is grabbed from the server using ...
0
votes
1answer
548 views

CodeChef Matches challenge

I am solving some problems from CodeChef but I am stuck on the Matches problem: Ari and Rich are playing a pretty confusing game. Here are the rules of the game: The game is played with ...
3
votes
0answers
99 views

Naive Implementation of A Least Recently Used (LRU) Cache Memoiser

I wrote code to (naively) perform lru memoisation. I tried to write it in a functional programming style, and so did not make use of any global variables. My Code ...
1
vote
1answer
36 views

Naive Implementation of Automatic Memoisation

I wrote code to (naively) perform automatic memoisation. I tried to write it in a functional programming style, and so did not make use of any global variables. My Code ...
4
votes
3answers
7k views

Knapsack problem - recursive approach with memoization

This post is based on the 0-1 Knapsack problem. I came across this problem in Assignment #4 of Professor Tim Roughgarden's course Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming on ...
2
votes
1answer
57 views

Number of way to render an amount of money

I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain ...
2
votes
3answers
182 views

List of Happy Numbers in scala

Definition of Happy numbers taken from Wikipedia. A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits ...
10
votes
2answers
2k views

Recursive Fibonacci in Rust with memoization

I'm trying to come up with an "elegant" way of calculating Fibonacci for number in Rust, using recursion and memoization (self-imposed requirements). This is what I have so far: ...
1
vote
1answer
196 views

Longest Collatz sequence in Scala

I am trying to find the longest Collatz Sequence: Which starting number, ≤ N, produces the longest chain? If many possible such numbers are there print the maximum one. (1 ≤ N ≤ 5×106) I tried ...
2
votes
1answer
854 views

Determine all ways a string can be split into valid words, given a dictionary of all words

This function word_break(s, dictionary) receives a string s and a set of all valid words ...
6
votes
2answers
247 views

Thread-Safe Garbage Collectible Memoizer

I am working on a little thread-safe, garbage collectible memoizer for Funcs in C#. The goals: Make it easy to Memoize deterministic functions. Make sure invocation of a memoized Func with a given ...
3
votes
0answers
1k views

Robot on a Grid: Find a path between two corners with forbidden cells on the road

Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
2
votes
1answer
63 views

Dynamic programming to solve two printers with different speeds

I solved this problem using a Class, but thought I might try to figure out this memoization thing. Problem There are two printers that print pages at different speeds (X, Y). What is the minimum ...
1
vote
1answer
414 views

Recursive Fibonacci in Java

I just started learning recursion and memoization, so I decided to give a simple implementation a shot. Works with some simple test cases I came up with. Is there anything I can add to make this more ...
7
votes
2answers
691 views

Project Euler 357 prime number generator in Python 3

I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks: Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, ...
2
votes
1answer
204 views

Check the equality for each subset of a string S against the target T and return a count

I wrote the following code to solve this leetcode problem: ...
5
votes
1answer
873 views

Python: wild card pattern matching with memoization

Here is my take on wild card pattern matching with memoization. I would appreciate comments on clarity of the code, as well as suggested ways to improve readability and maintainability (for bigger ...
2
votes
0answers
498 views

Leetcode 10: Regular Expression Matching

Problem statement Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching ...
1
vote
0answers
390 views

ADACOINS - Ada and Coins TLE (SPOJ)

Ada the Ladybug has several coins in her wallet. She is wondering, how many different values [sum of some subset of coins] is she able to make (in given range). Input The first line contains two ...
1
vote
0answers
193 views

Buying Apples - SPOJ

THIS is the link to the problem on SPOJ. I thought it would be better to give the link to the problem instead of me trying to explain as the question is not very clear at first sight. I was able to ...
2
votes
2answers
252 views

Transform String a into b

You can perform the following operation on some string a: Capitalize zero or more of a's lowercase letters at some index i (i.e., make them uppercase). Delete all of the remaining lowercase ...
4
votes
1answer
287 views

Memoizing in PostScript

The pusherr and poperr procedures maintain an internal stack as a lisp-like linked-list. It's a little slower than an earlier ...
1
vote
0answers
126 views

x as the sum of unique integers raised to power n

I've done this problem using recursion. But I'm not sure that could this be optimized for bigger values of x using memoization. ...
11
votes
2answers
2k views

Memoizing or caching Bash function results

Update: I've implemented several of the features suggested below and packaged the improved code into a dedicated project: bash-cache. I display a number of expensive operations in my Bash prompt (e.g....
6
votes
1answer
497 views

Locating the largest Collatz Sequence with memoization

Inspired by this question I wrote a memoized form of the collatz sequence calculator. The idea was to cache the sequence lengths for as many sequences as possible, from 0 to some value. I managed to (...
3
votes
1answer
4k views

Google Foobar Level 3 - Lucky Triples (Find the Access Codes)

I have been working on this problem for 3 days now. I wrote a piece of java code that works perfectly on my machine testing in Eclipse, but when I put it in Foobar, it either returns "Error(400) Bad ...
5
votes
2answers
512 views

Calculating the count of integer partitions of a number (uses stateful vectors internally)

I've written a Haskell function to count the number of partitions of an integer - it's basically an implementation of the same algorithm as this one, using Euler's Pentagonal Number Theorem: $$P(n) = ...
1
vote
1answer
249 views

Binary Option Pricing using Card Game

I shuffle a deck of cards(with an equal number of red and black cards) and start dealing them face up. After any card you can say “stop”, at which point I pay you $1 for every red card dealt and ...
4
votes
1answer
209 views

Multiplying two- or three-dimensional arrays with broadcasting

Background Disclaimer: Skip if you are not interested in the background. The code is far far simpler than this. The problem is more about programming than math. Here is the definition of ...
2
votes
1answer
408 views

Memoization via template

This is kind of follow up of this question on stack overflow... I wrote the following to utilize memoization for functions that take a single parameter and return a value: ...
4
votes
2answers
2k views

Memoization with factorial in Python

I wrote a Python module to learn about memoization, and I have some questions on what I did. How pythonic is this? Does it make a difference if I used a class attribute instead of a function ...
2
votes
1answer
58 views

Find offset that minimizes squared difference between two vectors of different size

I am working on a project where the hotspot is some code that is supposed to find an offset, such that the squared differences between a reference vector and a given vector becomes minimal. The core ...
2
votes
2answers
545 views

Memoizing decorator with retries - now with backoff added! (Part 3)

A continuation of Memoizing decorator with retries, part 2, and related to https://codereview.stackexchange.com/a/133493/47529. I liked my decorator before, but especially in my original use case of a ...
5
votes
3answers
347 views

Memoizing decorator with retries, part 2

A while ago I asked this question Memoizing decorator that can retry and then promptly forgot about it. I more recently saw Python decorator for retrying w/exponential backoff and wanted to add ...
13
votes
1answer
217 views

Multi-function memoizator and multi-type container

I'm trying to write a multiple functions memoizator, which I've talked about here. The main problem is creating a container containing different and heterogenous functions. I found a working solution,...