# Programming Galore!

Hi Brilliant!

I've been missing the programming section and I thought we could create a thread where we post challenging programming problems. This is your opportunity to suggest perplexing problems and a chance to parade your programming skills! I'm looking for elegant problems and solutions.

Programming is an art! Don't just write a solution that works, but aim to write an algorithm that is concise so that if you give it to another programmer, they can understand it with ease.

Post your programming problems and challenge the Brilliant community to solve them!

Vote up if you have a passion for programming!

Note by Mark Mottian
4 years, 5 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

This is a somewhat tough problem from the world of numerical analysis and matrix theory:

In scientific computing, a useful metric for the "size" of a matrix is its infinity norm, which is a total function on the space $$\|\cdot\|_\infty : \mathbb{R}^{n \times m} \to \mathbb{R}$$ that gives the maximum row sum of the absolute value of its input (i.e. you take the absolute value of a matrix and sum all of its rows, then you return the largest of those sums).

A matrix is lower bidiagonal if it looks like $\left(\begin{array}{cccc}l_1 \\ r_2 & l_2 \\ & r_3 & l_3 \\ && r_4 & l_4\end{array}\right)$

Suppose $$A$$ is lower bidiagonal, write a function invnorm(l,r) that takes in a list of n numbers l (denoting the main diagonal of A) and another list of n-1 numbers r (denoting the first subdiagonal of A) and return the infinity norm of $$A^{-1}$$.

def invnorm(l,r):
...
return infinity norm of A^-1


Recommended Extensions (these require actual math):

1. Make invnorm run in $$O(n^2)$$ time (with respect to n the sive of l). Hint: the inverse of A is lower triangular, and it turns out that with a bit of cleverness, you can construct each entry of A in constant time if you know a few of the other entries of A, a la the spirit of dynamic programming.

2. Make invnorm run in $$O(n)$$ time. Hint: a) solving the system $$Ax = b$$ takes $$O(n)$$ time by dynamic programming; b) prove an invariance theorem on the properties of $$\|A^{-1}\|$$ with respect to $$A$$, then construct an invariant transformation under the mapping $$\|\cdot^{-1}\|_\infty$$ which, combined with a), allows you solve the problem quickly.

3. (Open) Is it possible to do better than $$O(n)$$ time, what about for approximations?

- 4 years, 5 months ago

- 4 years, 5 months ago

For those who really want a challenge, check out Prime Challenge

- 4 years, 5 months ago

Programming Challenge: South African Programming Olympiad 2000 #4

Given a string of digits 0-9. Group the adjacent digits to form numbers, in such a way that their sum will equal a certain given total T. A digit may only belong to one number. Input: A string of digits 0-9 followed by a second line containing the number T. Output: A string of groups. Output the groups as they appear in the original string, separated by commas.

Example

Input

String: 2415043

Total -T: 289

Output

Solution: 241, 5, 0, 43

Test you programme with the following:

a) String: 2237450 and T: 104

b) String: 1848935 and T:38

- 4 years, 5 months ago

What are the constraints of the length of the string and the value of T?

- 4 years, 5 months ago

There are no constraints listed in the problem statement. I've posted the problem exactly the way it appears in the question paper.

- 4 years, 5 months ago

Programming Challenge: South African Programming Olympiad 2013 #3

A number is well-ordered when its digits are in numerically ascending order. E.g. 147 is well-ordered but 174 is not. In a well-ordered number, each of the digits 1-9 may only be used once. Write a program that will calculate the sum of all the well ordered numbers that are possible with a fixed number of digits.

Example:

Input: 2

Output: 1440

(Explanation: The programme added up all the well-ordered two-digit numbers. That is, 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 34 + 35 + 36 + 37 + 38 + 39 + 45 + 46 + 47 + 48 + 49 + 56 + 57 + 58 + 59 + 67 + 68 + 69 + 78 + 79 + 89)

- 4 years, 5 months ago

To be honest, you can simply hard-code all the solutions: there are only 9 test cases (1 to 9). For example:

n = input()
if n == 1:
print 45  # 1+2+3+4+5+6+7+8+9
if n == 9:
print 123456789
# insert more


However, I have no better idea to do the actual computation without bruteforcing everything. Any ideas?

- 4 years, 5 months ago

This is ineffective! How would one solve the problem if the input is some large number such as 100 (as an explicit example)? Again, there are no constraints listed in the original question paper.

- 4 years, 5 months ago

When N > 9, the answer is 0; there is no number with N digits whose digits are strictly increasing.

The problem is different when you are given both N and the base. (In this case, without the base, it's assumed to be 10.)

- 4 years, 5 months ago

Oh! That makes more sense.

- 4 years, 5 months ago

Challenge: South African Programming Olympiad 2000 #2

Imagine an alphabet that has been designed for a keyboard with only 2 keys: left and right. The keyboard sends the following signals: Left key pressed (L), Left key released (M), Right key pressed (R) and Right key released (S). Certain patterns of key presses or releases create meaning – in this case, letters of the alphabet.

Signals:

LM --> A

RS --> N

LRSM --> C

LRMS --> E

RLSM --> L

RLMS --> T

Task: Recognise the letters from the signals and print the message

Input: A string of letters Output: The resulting message

Example:

Input: RLMSLRMSRSRLMS

Output: TENT

Test Data:

i) RLMSLMRLSMLRMSRSRLMS

ii) LRSMLMRLMSRLMSRLSMLRMS

- 4 years, 5 months ago

What is the most efficient algorithm to determine the following?

i) The lowest common multiple (LCM) of two (or more positive integers). E.g. the LCM of 10, 15 and 20 is 60

ii) The greatest common divisor (GCD) of two (or more positive integers). E.g. the GCD of 10, 15 and 20 is 5

iii) The prime factorisation of a single positive integer. E.g. the prime factorisation of 693 = 3x3x7x11

- 4 years, 5 months ago

ii) Euclidean algorithm is a sufficiently fast one (at the order of $$O(n^2)$$ where $$n$$ is the average number of bits of the numbers). A method to compute the GCD of more than two numbers is by computing the GCD of each integer and the current GCD, which probably means $$O(n^{2k-2})$$ where $$n$$ is the average number of bits of the numbers and $$k$$ is the number of numbers.

i) Use Euclidean algorithm again. Since LCM of $$a,b$$ is simply $$\frac{ab}{\gcd(a,b)}$$, we can compute it in $$O(n^2)$$ for the GCD, then probably $$O(n^2)$$ too for division of $$a$$ with $$\gcd(a,b)$$, and then probably $$O(n^2)$$ again for the multiplication with $$b$$, for an overall of $$O(n^2)$$. So it will have roughly the same complexity as GCD, but will be much slower than it (partly due to threefold computation, partly because LCM grows in size while GCD shrinks as more numbers are processed, thus making multiplications/divisions harder).

iii) Widely believed to be NP-Intermediate; no polynomial time algorithm is known. The most efficient algorithm known is general number field sieve.

- 4 years, 5 months ago

I remember seeing a formula once that outputs the largest prime factor of any positive integer. I know the article (Dudley, U., Formulas for primes, Math. Mag., 56 (1983) 17-22) but can't really find the formula.

- 4 years, 5 months ago

Write programs to determine what is outlined above.

- 4 years, 5 months ago

I guess this is a really popular one..But try finding the millionth prime number.

- 4 years, 5 months ago

Programming Challenge: British Informatics Olympiad 2002 Sample Paper #1

A group of friends are standing in a circle, playing a game. They proceed around the circle, chanting a rhyme and pointing at the next person (clockwise) on each word. When the rhyme finishes whoever is being pointed at leaves the circle. They then start again, pointing where they left off, and the game continues until only one person is left.

For example, suppose there are six friends (numbered 1 to 6) standing around the circle and the rhyme is "Eenee, Meenee, Mainee, Mo!". The first person to leave the circle is number 4, followed by 2 then 1, 3 and 6. Number 5 is left.

Sample run

Number of friends: 7

Words in rhyme: 3

Number 4 is left

Write a program that inputs two numbers (each between 1 and 1000 inclusive), the first being n, the number of friends, and the second the number of words in the rhyme. The output should be the number of the last person left.You should assume that the friends are numbered (clockwise) from 1 to n, and that the count begins at person 1.

- 4 years, 5 months ago

def J(n,k):
return 0 if n == 1 else (J(n-1,k)+k)%n

n = int(raw_input('Number of friends: '))
k = int(raw_input('Words in rhyme: '))
print 'Number %s is left '%(J(n,k) + 1)


- 4 years, 5 months ago

Python Solution:

def game(n, w):

friends = [x for x in range(1, n + 1)]
pos = 0

while len(friends) > 1:
pos += w - 1
pos %= len(friends)
friends.pop(pos)

return friends[0]

n_in = input('Number of friends: ')
w_in = input('Words in rhyme: ')

print(game(n_in, w_in))


Works by looping through and removing one person at a time.

- 4 years, 5 months ago

Challenge: Can you do better than $$O(n)$$?

- 4 years, 5 months ago

Programming Challenge: South African 2013 Programming Olympiad #4

(I've managed to come up with a solution this problem, however, it's definitely not the most elegant.)

An anagram of a word contains the same letters as the original word, but in a different order.

Write a program that will calculate how many anagrams can be made with a given word - NOT counting the word itself. Anagrams that have the same letter-order may only be counted once. The words given will always be lower case.

Example 1:

Input: cat

Output: 5 (Explanation: the accepted anagrams for "cat" are: "cta", "act", "atc", "tac", "tca" which is a total of 5)

Example 2:

Input: see

Output: 2 (Explanation: the accepted anagrams for see are: "ese" and "ees". Although "ees" can be made up in two ways by rearranging the letters of "see", it only counts as a single anagram - because the final word in the same. A total of 2.)

- 4 years, 5 months ago

from math import factorial

def check_duplicates(s):
char_count = {}

for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1

return char_count

def n_anagrams(s):
char_count = check_duplicates(s)
count = factorial(len(s))

for key in char_count:
count /= factorial(char_count[key])

return count - 1

print(n_anagrams('cat'))

The algorithm works by counting how many duplicates there are of each letter, finding how many total anagrams there are with repetition, then dividing by the factorials of the number of repeats for each letter. Finally, the program subtracts $$1$$ to remove the original string. I have tried the program with strings up to $$1000$$ characters long without exceeding $$0.0$$ seconds.

- 4 years, 5 months ago

Here's my ridiculous code (don't judge):

import math
userinput = raw_input("Enter word: ")
word = list(userinput)

a = word.count('a')
b = word.count('b')
c = word.count('c')
d = word.count('d')
e = word.count('e')
f = word.count('f')
g = word.count('g')
h = word.count ('h')
i = word.count('i')
j = word.count('j')
k = word.count('k')
l = word.count('l')
m = word.count ('m')
n = word.count('n')
o = word.count('o')
p = word.count('p')
q = word.count('q')
r = word.count('r')
s = word.count('s')
t = word.count('t')
u = word.count ('u')
v = word.count('v')
w = word.count('w')
x = word.count('x')
y = word.count('y')
z = word.count ('z')

denominators = [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z]
denominator = 1

for values in denominators:
denominator = denominator * math.factorial(values)

numerator = 0
numerator = math.factorial(len(userinput))



- 4 years, 5 months ago

Here, I again modify the program (without modifying the logic behind it), lest your program goes to The Daily WTF:

import math
userinput = raw_input()
word = list(userinput)

denominator = 1
for i in range(26):
denominator *= math.factorial(word.count(chr(97+i))))

numerator = math.factorial(len(userinput))
print (numerator/denominator)-1


I don't get why you put numerator = 0 and answer = 0 while you immediately assign them something else.

- 4 years, 5 months ago

This is exactly what I wanted! I wanted someone to improve my code whilst not altering the logic behind it. You are fantastic!

- 4 years, 5 months ago

- 4 years, 5 months ago

- 4 years, 5 months ago

The entire Brilliant community will try their best to answer your questions.

- 4 years, 5 months ago

I really like your solution. I didn't think of making a dictionary to count each letter (I haven't used this enough). We had the same approach, but yours is more concise. I've really learnt a lot from your solution. Thank you so much!!

- 4 years, 5 months ago

Not particularly efficient but at least it's simple:

from itertools import permutations

def count_anagrams(s):
return len(set(permutations(s))) - 1


- 4 years, 5 months ago

This is really simple! Well done! It takes quite a while for longer strings though.

- 4 years, 5 months ago

Here's a fairly simple problem from CodeChef.com.

And one more suggestion I have - programming enthusiasts can also share their views about popular algorithms as well.

- 4 years, 5 months ago

Thanks for an awesome problem! Do you have any other suggestions or problems? I think posting popular algorithms (in this thread) is an excellent idea!

- 4 years, 5 months ago

Here's my solution (using Python) to the problem you suggested:

import math
testcases = input("Enter number of testcases: ")
y =  []

def fact(n):
a1 = math.factorial(n)
y.append(a1)

for x in range (1, testcases+1):
a = input("Number: ")
fact(a)

print
print ("Output:")

for values in y:
print values


- 4 years, 5 months ago

In programming problems, you must give the exact output as required. Your "Enter number of testcases:", "Number:", and "Output:" make your program fails the problem.

- 4 years, 5 months ago

Thanks for the advice. I put those keywords in the programme to aid better understanding of the code. The programme still works 100% (as outlined in the problem statement) if I remove those keywords.

- 4 years, 5 months ago

Usually people comment their code instead of printing stuff to the standard output... But yeah.

Here's how your program can be shortened:

import math
testcases = input()

for i in range(testcases):
a = input()
print math.factorial(a)


Standard input and standard output are separate, so what you output will not be broken by what the judge will input. For example, what the judge will see will not be:

4
1
1
2
2
5
120
3
6


But:

(Standard input)
4
1
2
5
3

(Standard output)
1
2
120
6


(At least that's what I know.)

- 4 years, 5 months ago

Very elegant!

- 4 years, 5 months ago

- 4 years, 5 months ago

The following is probably the best website for programming purposes ::

- 4 years, 5 months ago

Project Euler is awesome! I also use it. After a while, it does get a bit tedious. Why don't you put forward your favourite problem from Project Euler for us to solve?

- 4 years, 5 months ago

sorry

- 4 years, 5 months ago