Questions tagged [optimization]
For challenges focusing on the optimization of an aspect not covered by other tags. (not a winning criterion)
134
questions
11
votes
7
answers
638
views
Shortest restricted superstring
Given two sets of strings, \$ D \$ and \$ R \$, find the shortest string which contains every string in \$ D \$, but contains none of the strings in \$ R \$.
There are almost always multiple possible ...
- 18.4k
19
votes
8
answers
2k
views
Optimally break a string into words
Given a string, like potatocarrot, break it into the smallest number of substrings possible. These substrings can consist either be a single character, or one of a ...
- 17k
12
votes
1
answer
325
views
Wash clothes as quickly as possible
It's laundry day, and you have lots of clothes that need to be washed. Wanting to have as much time left over for code golf as possible, you hope to optimize how quickly you wash and dry them all.
You ...
- 17k
16
votes
11
answers
2k
views
Satisfy as many people as possible
There are times when a large number of people need to choose something. They all want to get the stuff they choose, obviously, but it's impossible to please everyone that way, so a usual compromise is ...
- 2,659
3
votes
2
answers
228
views
Implement constant-latency branchless multiplication efficiently
Modern hardware can perform multiplication very fast in a constant latency of 3~4 cycles. But some tiny chips for embedded environments sometimes lack hardware multiplication, which has to be emulated ...
- 2,121
19
votes
4
answers
539
views
Egyptian fractions summing to n
An "Egyptian fraction" is a list of distinct fractions with a numerator of \$1\$. For example:
\$
\frac 1 1+ \frac 1 2 + \frac 1 3 + \frac 1 6
\$
The "size" of an Egyptian ...
- 84.9k
11
votes
6
answers
851
views
High throughput prime numbers
This challenge is inspired by the High throughput Fizz Buzz challenge.
The goal
Generate a list of prime numbers up to 10,000,000,000,000,000. The output of primes should be in decimal digits followed ...
- 2,121
32
votes
10
answers
5k
views
Who Is Kevin Bacon?
You may know the game The Six Degrees of Kevin Bacon, based on the conjecture that every actor in Hollywood can be connected to Kevin Bacon by no more than 6 "co-star" relations, so Kevin ...
- 18.4k
14
votes
21
answers
2k
views
Constructing Solar Panels from Squares
I'm designing a new space station for generic super-villain purposes (something something megalaser), but I'm having trouble designing the solar panels.
My genius team of scientists can calculate ...
- 11.1k
21
votes
21
answers
2k
views
Hunt for discount
Story
My local pizza delivery introduced new discount. You get 50% discount from every second item on your order.
But being greedy capitalists, they forgot to mention that they will rearrange items ...
- 669
7
votes
2
answers
321
views
Largest Compatible Maze
Background
Consider an \$n\times n\$ grid, where each cell is either empty (denoted by .) or a wall (denoted by #). We say that ...
- 6,216
18
votes
7
answers
1k
views
Square root multiples
This code-challenge is based on OEIS sequence A261865.
\$A261865(n)\$ is the least integer \$k\$ such that some multiple of \$\sqrt{k}\$ is in the interval \$(n,n+1)\$.
The goal of this challenge is ...
- 8,097
4
votes
2
answers
399
views
Minimal Pairing
Your program should take two lists, where each entry (a positive integer) represents the number of members of some group, as input. These lists will have the same sum but may have different lengths.
...
- 2,997
2
votes
0
answers
61
views
Find two contiguous subarrays with the greatest difference [closed]
Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn'...
- 121
7
votes
3
answers
487
views
Swaps to Sort an Array
You are given an array \$A\$, which may contain duplicate elements. In each swap, you may swap the value of any two indices \$i, j\$ (i.e. switch the values of \$A_i\$ and \$A_j\$). What is the least ...
- 659
19
votes
1
answer
913
views
Gerrymander North Carolina
The challenge
How well can you gerrymander North Carolina into 13 voting districts?
In this challenge, you use the following files to draw different maps for Republicans and Democrats.
File 1: ...
- 2,229
10
votes
2
answers
918
views
Find the largest root of a polynomial with a neural network
The challenge
Find the smallest feedforward neural network such that, given any 3-dimensional input vector \$(a,b,c)\$ with integer entries in \$[-10,10]\$, the network outputs the largest (i.e., "...
- 2,229
17
votes
1
answer
1k
views
Sort with a neural network
The previous neural net golfing challenges (this and that) inspired me to pose a new challenge:
The challenge
Find the smallest feedforward neural network such that, given any 4-dimensional input ...
- 2,229
23
votes
2
answers
1k
views
Create a uniquely solvable crossword ... without clues
Can you imagine solving the New York Times crossword puzzle without any clues? Maybe not with all of the creativity and new words and phrases appearing in modern crosswords, but with a fixed word ...
- 2,509
18
votes
14
answers
1k
views
Permutations in Disguise
Given a \$n\$-dimensional vector \$v\$ with real entries, find a closest permutation \$p\$ of \$(1,2,...,n)\$ with respect to the \$l_1\$-distance.
Details
If it is more convenient, you can use ...
- 43k
30
votes
3
answers
746
views
Heavy Box Stacking
You have a bunch of heavy boxes and you want to stack them in the fewest number of stacks possible. The issue is that you can't stack more boxes on a box than it can support, so heavier boxes must go ...
- 9,791
6
votes
1
answer
464
views
Multiplication in Brainfuck - minimum number of evaluations [closed]
Given two numbers in tape location #0 and tape location #1 in Brainfuck, compute their product into another tape location (specify with answer). Optimize for the least amount of time-units used, where ...
27
votes
13
answers
3k
views
Make me a minimum magic sum
Keeping this challenge short.
You are given 4 numbers: p1, p2, p3 and p4.
The magic sum of the numbers are defined as follows:
...
- 1,193
30
votes
2
answers
1k
views
Can a neural network recognize primes?
Background
Recognizing primality seems like a poor fit for (artificial) neural networks. However, the universal approximation theorem states that neural networks can approximate any continuous ...
- 2,509
9
votes
3
answers
464
views
Minimum-cost flow problem
A flow network is a directed graph G = (V, E) with a source vertex s ϵ V and a sink vertex ...
user45941
17
votes
3
answers
992
views
Plight of the Concorde
Background
The traveling salesman problem (TSP) asks for the shortest circuit that visits a given collection of cities. For the purposes of this question, the cities will be points in the plane and ...
- 2,509
16
votes
1
answer
392
views
Optimizing swiping across a 1D keyboard
This is a code-challenge with a custom scoring system, where the lowest score wins.
Introduction
Many smartphones allow to enter text by swiping your finger across the 2D virtual keyboard. This ...
- 166k
17
votes
3
answers
495
views
Optimize my wings order
This tweet lists the possible orders for Wings of a Chinese restaurant1:
When ordering Pizza I usually calculate what size gives me the best Pizza-price ratio which is a simple calculation. However ...
- 16.3k
6
votes
3
answers
248
views
Optimizing edge selection from a list of numbers
You are given a list, L, with the length N. L contains N random positive integer values. You are only able to select from the outer edges of the list (left/right), and after each selection every value ...
- 61
26
votes
2
answers
1k
views
Optimize Compiler for simple Reverse Polish Notation Programming Language
Description
Imaginary programming language (IPL) uses Polish Reverse Notation. It has the following commands:
i -- input number and push it to the stack
o -- non-destructive output top of the stack ...
- 329
21
votes
11
answers
2k
views
Fruit bagging factory
Your mission is to build an algorithm (program or function) that can optimize packing fruit from a conveyor belt into bags to be sent off to retailers, optimizing for a largest number of bags.
Each ...
- 4,917
9
votes
1
answer
299
views
+- knapsack problem
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value ...
- 3,532
11
votes
2
answers
531
views
Egg hunting in Collatz style
Inspired by The Great API Easter Egg Hunt!
Summary
Your task is to search for a predetermined integer in the "Collatz space" (to be explained later) using the fewest step possible.
...
- 3,566
7
votes
4
answers
455
views
Minimize Least Used Binary Bits in Fractions
Introduction
For a given rational number r, find a pair of integers p,q so that p/q=r and ...
- 3,566
18
votes
8
answers
665
views
Sort by shuffling blocks
Block shuffle sort
The block shuffle sort is a (rather artificial) method of sorting a list.
It works as follows, illustrated by an example.
...
- 42k
18
votes
8
answers
1k
views
1D Hopping Array Maze
Inspired by We do tower hopping and related to 2D Maze Minus 1D
Introduction
Your task is to find the shortest path to get out of an array maze following specified rules.
Challenge
A 1D array a with n ...
- 3,566
17
votes
14
answers
2k
views
We do tower hopping
Task
Given an array of non-negative integers a, determine the minimum number of rightward jumps required to jump "outside" the array, starting at position ...
- 784
22
votes
2
answers
1k
views
Integer Linear Programming
Introduction
Write a solver for integer linear programming.
Challenge
Your task is write a solver for integer linear programming (ILP). In ILP, linear inequalities of a set of unknowns (all of which ...
- 3,566
13
votes
1
answer
723
views
Can you outgolf Bill Gates?
Pancake sorting is the colloquial term for the mathematical problem of
sorting a disordered stack of pancakes in order of size when a spatula
can be inserted at any point in the stack and used to flip ...
- 45k
317
votes
23
answers
43k
views
Write Moby Dick, approximately
Here is a 1.2Mb ASCII text file containing the text of Herman Melville's Moby-Dick; or, The Whale. Your task is to write a program or function (or class, etc. -- see below) which will be given this ...
- 7,102
15
votes
1
answer
370
views
Strategic Vanishers
This post is loosely inspired by this mathoverflow post.
A Vanisher is any pattern in Conway's Game of life that completely disappears after one step. For example the following pattern is a size 9 ...
- 84.9k
42
votes
16
answers
4k
views
How small can it get?
Starting with a positive integer N, find the smallest integer N' which can be computed by repeatedly dividing N by one of its digits (in base-10). Each selected digit must be a divisor of N greater ...
- 166k
19
votes
1
answer
689
views
Advent Challenge 1: Help Santa unlock his present vault!
Next >>
Descriptive Keywords (for searching): Make Two Matrices Equivalent, Overlap, Array, Find
Challenge
Santa has had a history of elves stealing presents from his vault in the past, so this ...
- 40.2k
5
votes
1
answer
303
views
Bobby's Booby-Trapped Safe
Bobby's booby-trapped safe requires an n-digit code to unlock it. Alex has a probe which can test combinations without typing them onto the safe. The probe responds Fail if no individual digit is the ...
- 2,723
25
votes
4
answers
805
views
Minimum rectangle cover
Rectangle covers
Suppose you have a matrix of bits, for example the following.
1 1 0 0 0 1 1 0
1 1 1 1 0 1 1 1
0 1 1 1 0 1 1 1
1 1 0 1 1 1 1 0
1 1 0 1 1 1 0 1
...
- 42k
6
votes
2
answers
276
views
Fuzzy distances to coordinates
This challenge is similar to my previous one, but has a twist that makes it significantly more difficult.
There are n people on a 2D plane. Using distances between them we're going to find their ...
- 38.6k
8
votes
8
answers
343
views
Piles and Piles of Pebbles
My job is stacking pebbles into triangular piles. I've only been doing this for a century and it is already pretty boring. The worst part is that I label every pile. I know how to decompose pebbles ...
- 15.9k
19
votes
8
answers
840
views
Optimal path through a matrix
Given a matrix consisting of positive integers, output the path with the lowest sum when traversing from the upper left element to the bottom right. You may move vertically, horizontally and ...
- 45k
1
vote
0
answers
137
views
Bucket Brigade! [closed]
Inspired by this, this and this.
So, now that the evil farmer has set your field on fire, you naturally want to put it out. You have a bunch of friends who all have buckets, and you want a program ...
- 6,889
24
votes
10
answers
2k
views
Efficient Robot Movement
Disclaimer: The story told within this question is entirely fictional, and invented solely for the purpose of providing an intro.
My boss has gotten a new toy robot, and he wants me to help program ...
- 6,889