Questions tagged [memoization]
An optimization technique where function calls are cached to avoid duplicate computations.
87
questions
0
votes
1
answer
115
views
Leetcode: 2327. Number of People Aware of a Secret
On day 1, one person discovers a secret.
You are given an integer delay, which means that each person will share the secret with a new person every day, starting from delay days after discovering the ...
- 1
2
votes
1
answer
167
views
k-dice Ways to get a target value
I'm trying to solve the following problem:
You have a k-dice.
A k-dice is a dice which have k-faces and each face have value written from 1 to k.
Eg. A 6-dice is the normal dice we use while playing ...
- 212
2
votes
2
answers
146
views
Generate the number of partitions of each integer
I've coded a program that calculates the number of partitions of n into at least two distinct parts, and is relatively quick too (about N^1.5 complexity). For input 30 000 it takes roughly 4 seconds. ...
- 21
0
votes
1
answer
59
views
Improving performance with a react modal where the component runs on every page
I have a simple cookie popup where the component technically runs on every page, giving the user the option to accept all or essential cookies. Once they accept an option, the popup no longer shows. ...
- 537
1
vote
0
answers
150
views
Memoize using Map
Trying to implement a simple memoize using Map, so that it can support Symbols and Objects using reference, please let me know if I am missing anything
...
- 101
1
vote
0
answers
1k
views
Add to Favourite List example - working but with performance issues
I am building a small framework for e-commerce or blog app using React.
One of the features of this framework is an "Add to Favourite List" function.
The ...
- 11
1
vote
1
answer
129
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,944
2
votes
1
answer
169
views
10
votes
1
answer
1k
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 ...
- 165
3
votes
1
answer
258
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 ...
- 133
6
votes
2
answers
815
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 ...
- 297
0
votes
3
answers
117
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
1
answer
446
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: ...
- 21
1
vote
1
answer
127
views
Generic memoize function in Swift
I need to perform some expensive calculation, such as determining a Fibonacci number:
...
- 119
6
votes
1
answer
140
views
Generic memoize utility function for pure functions
Given the following generic memoize utility for pure functions with type hints:
...
- 71
6
votes
1
answer
373
views
Memoizing a tree's parent pointers in Python
I have a simple binary tree that has no parent pointers.
...
- 223
3
votes
1
answer
153
views
2
votes
2
answers
182
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 ...
- 167
3
votes
0
answers
95
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 ...
- 799
3
votes
1
answer
89
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.
...
- 33
1
vote
0
answers
317
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 ...
- 213
0
votes
1
answer
629
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
0
answers
109
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,806
1
vote
1
answer
38
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
...
- 1,806
4
votes
3
answers
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 ...
user188780
2
votes
1
answer
60
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 ...
- 21
2
votes
3
answers
386
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 ...
- 395
12
votes
2
answers
3k
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
1
answer
210
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 ...
- 109
3
votes
1
answer
1k
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 ...
- 31
6
votes
2
answers
280
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 ...
- 503
3
votes
0
answers
2k
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 <...
- 3,480
2
votes
1
answer
76
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 ...
- 7,149
1
vote
1
answer
448
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 ...
- 117
7
votes
2
answers
731
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, ...
- 507
2
votes
1
answer
228
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:
...
- 21
5
votes
1
answer
902
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 ...
- 351
2
votes
0
answers
556
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 ...
- 2,396
1
vote
0
answers
419
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 ...
- 281
1
vote
0
answers
222
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 ...
- 281
2
votes
2
answers
271
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 ...
- 281
5
votes
1
answer
304
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 ...
- 2,008
1
vote
0
answers
128
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
12
votes
2
answers
3k
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....
- 387
6
votes
1
answer
605
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 (...
- 20.1k
3
votes
1
answer
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 ...
user124131
5
votes
2
answers
643
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) = ...
- 218
1
vote
1
answer
299
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 ...
- 135
4
votes
1
answer
225
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 ...
- 141
2
votes
1
answer
535
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:
...
