Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

For challenges focusing on the optimization of an aspect not covered by other tags.

4
votes
3answers
158 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 ...
13
votes
0answers
196 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 ...
20
votes
11answers
1k 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 ...
8
votes
1answer
222 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 ...
12
votes
2answers
398 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. Introduction ...
8
votes
4answers
412 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 ...
18
votes
8answers
602 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. ...
17
votes
7answers
432 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 ...
18
votes
14answers
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 0, or ...
22
votes
1answer
984 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 ...
12
votes
1answer
560 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 ...
280
votes
20answers
34k 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 ...
42
votes
16answers
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 ...
18
votes
1answer
590 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 ...
5
votes
1answer
240 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 ...
19
votes
3answers
530 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 ...
6
votes
2answers
249 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 ...
8
votes
8answers
310 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 ...
19
votes
8answers
669 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 ...
2
votes
0answers
105 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 ...
10
votes
2answers
1k views

Solve the Trolley Problem

Philosophers have long pondered the Trolley problem. Unfortunately, no human has solved this problem yet. Luckily, as programmers we can use computers to solve the problem for us! Input Your program ...
23
votes
5answers
555 views

Trigger the chutes and protect the jackpot

You are going to participate in a gameshow. One of the challenges works as follows: The first room contains a large number of identical balls. The second room contains a series of chutes, each of ...
24
votes
2answers
835 views

Optimize sorting, using “Sub-vector reversals”

This is a fewest-operations challenge where the objective is to sort a vector into ascending order using the fewest reversals. Your algorithm can only sort the vector using "sub-vector reversals"1, ...
18
votes
2answers
249 views

Island Golf #2: The Eccentric Hermits

This is the second in a series of Island Golf challenges. Previous challenge Two hermits have arrived on a desert island. Since they came seeking solitude, they wish to live as far away from each ...
7
votes
1answer
260 views

Shortest example of code that is compiled and increasing the optimization level makes it take longer

Just curious if someone can provide a short example of code that causes a compiler's optimizer to behave incorrectly: without optimization (or at lower optimization), code takes X seconds to run with ...
42
votes
6answers
2k views

Island Golf #1: Circumnavigation

This is the first in a series of Island Golf challenges. Next challenge Given an island in ASCII-art, output an optimal path to circumnavigate it. Input Your input will be a rectangular grid ...
14
votes
2answers
925 views

Count how many distance sequences are far from all others

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. Let P be a binary string of ...
1
vote
3answers
395 views

Give everyone T-Shirts

You're in charge of distributing T-Shirts to everyone. Simple enough, right? But remember, there are different sizes of T-Shirts, and you have to keep that in mind... Challenge Specifications There ...
11
votes
1answer
247 views

Split arrays and programs in half

Introduction You have been tasked to write a program that splits a rectangular integer array evenly in half (for whatever reason). This task is computationally intensive, but luckily you have a dual-...
2
votes
0answers
94 views

All-pairs shortest return paths without reusing edges [closed]

All-pairs shortest paths is a standard pathfinding problem. This is a twist on that. Definitions We are searching for paths on a directed graph. Graphs are defined by square matrices, for example <...
18
votes
3answers
1k views

Piet (Mondrian)'s Puzzle

For more information, watch this video, and go to A276523 for a related sequence. The Mondrian Puzzle (for an integer n) is the following: Fit non-congruent ...
29
votes
3answers
664 views

Choose the last card in a poker hand

Poker hands are ranked from best to worst as follows: Straight flush - five cards of sequential rank, all of the same suit Four of a kind - four cards of the same rank and one card of another rank ...
20
votes
29answers
820 views

Find the maximum deviation

This problem is "inspired" from a question that was originally asked on Quora (not for code golfing). I just want to make it a challenge for you guys (and my first problem submission here). Given an ...
28
votes
1answer
749 views

Given a list of circles, output the area of the smallest containing rectangle

You will be given a list of radii, you must output the area of the smallest rectangle which they will all fit in. For example, given the list [5,3,1.5] you would ...
24
votes
2answers
2k views

Compute the maximum number of runs possible for as large a string as possible

[This question is a follow up to Compute the runs of a string ] A period p of a string w is any positive integer ...
2
votes
0answers
238 views

What's so great about 1729? [closed]

This is not a duplicate of this question. This is asking for the nth number that can be represented as the sum of two cubes in two different ways, while that is asking for the n-th number that can be ...
17
votes
4answers
782 views

Actually Integer Metagolf

Background Actually (the successor to Seriously) is a stack-based imperative golfing language I created in November of 2015. Like many other golfing languages, it has one-byte commands that perform ...
16
votes
8answers
1k views

Find a maximal rectangle of 1s

Background I want to buy an plot of land and build my house on it. My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build ...
20
votes
4answers
500 views

“Finish work” as early as possible

Background Imagine for a moment that you have a mind-numbingly boring job. Every morning, you are given a collection of tasks that you should work on that day. Each task has a certain duration, and ...
12
votes
4answers
334 views

Choose Scenes for a Movie

Introduction Finally the movie company is financing your film. They have given you a maximum budget and they also set the running time of your movie. Now you can start with the pre-production. You ...
31
votes
4answers
639 views

Plurality Voting with Cellular Automata

There's a really important problem in cellular automata called the Majority problem: The majority problem, or density classification task is the problem of finding one-dimensional cellular ...
174
votes
137answers
16k views

What is the smallest positive base 10 integer that can be printed by a program shorter (in characters) than itself?

I think the question as above is clear, but just in case: Write a full program (not just a function) which prints a positive base 10 integer, optionally followed by a single newline. Qualifying ...
17
votes
2answers
520 views

Playing Billiards

In this code golf, you will have to determine the direction of the shortest shot that hits exactly n cushions before falling into a pocket. The billiard table is a 6 pocket pool table with the ...
3
votes
0answers
204 views

Robot optimization

Your task is to program a robot so that it reaches the hole in the ground on each of the maps within reasonable time. If the robot reaches the hole, it falls down into it and thus victory is assured, ...
4
votes
0answers
204 views

Finding the smallest grid of squares [closed]

Inspiration from Puzzling.SE. Suppose we have an m × n grid such that each element is a base 10 digit. We can read the numbers from such a grid so that we fix a starting element, go to one of the ...
17
votes
4answers
1k views

An optimization challenge with strange coins

You have n coins which each weigh either -1 or 1. Each is labelled from 0 to n-1 so you can ...
11
votes
1answer
545 views

An optimization version of the Hadamard problem

First, some definitions. A Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. The Hadamard conjecture proposes that a Hadamard matrix of ...
11
votes
4answers
388 views

Approximate Square Formation

Background I have a bunch of square-shaped boxes of equal size, and since I'm a neat person, I want to arrange them all into a square formation. However, their number is not necessarily a perfect ...
16
votes
4answers
693 views

Find the largest independent set in a high-dimensional lattice-like graph

For a given positive integer n, consider all binary strings of length 2n-1. For a given string ...
12
votes
2answers
300 views

Creasing for Loot

Introduction After a long battle, you have managed to defeat a Sphinx in a contest of riddles. The Sphinx, impressed with your skill, wishes to give you a reward commensurate with your cleverness, ...