2022 Developer Survey is open! Take survey.

Questions tagged [optimization]

For challenges focusing on the optimization of an aspect not covered by other tags. (not a winning criterion)

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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'...
user avatar
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 ...
user avatar
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: ...
user avatar
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., "...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 6,889