Questions tagged [memoization]
An optimization technique where function calls are cached to avoid duplicate computations.
3
votes
0answers
57 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
31 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
...
0
votes
0answers
58 views
Swift Knapsack problem using bottom-down (memoization) approach
I'm solving the "unbounded" variant of the knapsack problem, meaning the repetition of items is allowed. As in the Hackerrank version of the knapsack problem, I am returning the sum nearest to, not ...
3
votes
2answers
553 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
51 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 ...
1
vote
2answers
48 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 ...
5
votes
1answer
289 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
66 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
302 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 ...
5
votes
2answers
108 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 ...
2
votes
0answers
324 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
49 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 ...
1
vote
1answer
283 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
474 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
191 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
490 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
402 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
238 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
151 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
215 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
276 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.
...
9
votes
2answers
859 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....
6
votes
1answer
294 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
2k 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
347 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
173 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
153 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
211 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
1k 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
54 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
342 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
248 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 ...
9
votes
0answers
164 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,...
2
votes
1answer
81 views
Optimally allocating a resource with time-varying demand and cost
I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
4
votes
2answers
795 views
Memoized Collatz sequence
Here is one of my programs that utilized memoization and array to improve performance and memory usage. The performance seems satisfactory but the memory usage is ridiculous and I can't figure out ...
3
votes
1answer
58 views
caching decorator
I came up with a caching decorator for pure functions. Is it ok? Could it be better/simpler/faster?
...
10
votes
3answers
3k views
Find the Nth number divisible by only 2,3,5, or 7
I recently participated in a small friendly competition and this was one of the questions:
A number whose only prime factors are 2, 3, 5 or 7 is called a humble
number. The first 20 humble ...
2
votes
1answer
2k views
Implementation of Longest Common Subsequence
So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more ...
6
votes
1answer
984 views
Longest palindromic subsequence by memoization
I've written some code to solve the longest palindromic subsequence problem.
...
10
votes
1answer
10k views
Recursive Memoized Fibonacci in C++
I was reading an article on Wikipedia about memoization, so I wanted to try and apply it. I am fairly new to this subject, so I thought I'd start small. Does the program use memoization correctly? Is ...
4
votes
2answers
420 views
Memoized implementation of change-making algorithm
Recently, I wrote a simple program to solve the change-making problem. Rather than the tabular dynamic programming solution (described in the link), I tried to write a solution that uses memoization.
...
11
votes
2answers
1k views
Memoizing decorator that can retry
I have some tasks that I'd like to memoize because they connect to a rather slow network and have to wait for the data. Unfortunately this network can be a little finnicky and we get occasional ...
7
votes
2answers
972 views
Thread-safe memoizer
I have searched around but I was not able to find a complete implementation of the memoize pattern in a multithreaded context. It's the first time playing with thread synchronization. The code seems ...
12
votes
1answer
977 views
Detecting cycles in a directed graph without using mutable sets of nodes
I recently came across the classic algorithm for detecting cycles in a directed graph using recursive DFS. This implementation makes use of a stack to track nodes currently being visited and an extra ...
4
votes
2answers
478 views
5
votes
1answer
131 views
Levenshtein Distance with Haskell Vectors and Memoization
Is the following an effective way to implement the Levenshtein Distance with Haskell vectors?
...
3
votes
1answer
1k views
Memoization of Fibonacci using generic Int => Int helper
I'm trying to understand memoization using Scala. I took the Fibonacci sequence as an example because of the high cost of recursively computing numbers in the sequence without memoization.
...
1
vote
2answers
139 views
Lazy properties for the angle and length of a line segment
The code below shows the pattern I use to manage properties in my classes when I have the following requirements:
Some properties are slow to calculate and are rarely used, so I want them to be lazy
...
2
votes
0answers
656 views
Making a default value a property
I recently asked a question on StackOverflow, looking for a way to more easily turn a class attribute into a @property, but only if no other value has been provided ...
