Questions tagged [optimization]
For challenges focusing on the optimization of an aspect not covered by other tags.
110
questions
-5
votes
0answers
71 views
maximisation and minimization at the same time [closed]
I have a sorted list in python (sorted by the second element); example:
list = [(13,18),(6,12),(5,10),(4,3),(1,2),(0,0)].
I have to pick some elements from this list, such that sum of second numbers ...
2
votes
0answers
51 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'...
-6
votes
1answer
87 views
When relating to code golf do I call it “simplifying my code” or “optimizing my code” or something else [closed]
Like if I have this:
x=5
y=2
and I do this
x,y=5,2
Do I call this simplifying or optimizing or something else? What is the terminology here.
7
votes
3answers
373 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 ...
19
votes
1answer
859 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: ...
11
votes
2answers
869 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., "...
16
votes
1answer
816 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 ...
22
votes
2answers
990 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 ...
18
votes
14answers
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 ...
28
votes
3answers
724 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 ...
4
votes
1answer
308 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
13answers
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:
...
26
votes
2answers
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 ...
9
votes
3answers
264 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 ...
17
votes
3answers
911 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 ...
16
votes
1answer
349 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 ...
17
votes
3answers
440 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 ...
6
votes
3answers
237 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 ...
25
votes
2answers
961 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 ...
21
votes
11answers
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 ...
9
votes
1answer
281 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 ...
11
votes
2answers
490 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.
...
7
votes
4answers
443 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
647 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
576 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 ...
17
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 ...
22
votes
2answers
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 ...
13
votes
1answer
675 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 ...
305
votes
23answers
40k 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
634 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
272 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 ...
23
votes
3answers
700 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
265 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
339 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
779 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
125 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 ...
14
votes
3answers
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
582 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 ...
23
votes
2answers
926 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, ...
19
votes
2answers
288 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 ...
6
votes
1answer
270 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 ...
43
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 ...
13
votes
2answers
1k 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 ...
2
votes
3answers
408 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 ...
10
votes
1answer
274 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
110 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
<...
20
votes
3answers
2k 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 ...
31
votes
3answers
891 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
871 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 ...
