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!

#ComputerScience

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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):

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.
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.
(Open) Is it possible to do better than $O(n)$ time, what about for approximations?

Lee Gao - 7 years, 6 months ago

The solution to the first two extensions for those who want them and the pdfs

Lee Gao - 7 years, 6 months ago

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

Pi Han Goh - 7 years, 6 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)

Mark Mottian - 7 years, 6 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?

Ivan Koswara - 7 years, 6 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.

Mark Mottian - 7 years, 6 months ago

@Mark Mottian – 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.)

Ivan Koswara - 7 years, 6 months ago

@Ivan Koswara – Oh! That makes more sense.

Mark Mottian - 7 years, 6 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

Mark Mottian - 7 years, 6 months ago

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

Ivan Koswara - 7 years, 6 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.

Mark Mottian - 7 years, 6 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.

Kou$htav Chakrabarty - 7 years, 6 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

Mark Mottian - 7 years, 6 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.

Ivan Koswara - 7 years, 6 months ago

@Ivan Koswara – 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.

Mark Mottian - 7 years, 6 months ago

@Mark Mottian – 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:

But:

(Standard input)
4
1
2
5
3

(Standard output)
1
2
120
6

(At least that's what I know.)

Ivan Koswara - 7 years, 6 months ago

@Ivan Koswara – Very elegant!

Mark Mottian - 7 years, 6 months ago

@Ivan Koswara – Can u please answer some of my questions ., in JAVA .., PLEASE REPLY

Vamsi Krishna Appili - 7 years, 6 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!

Mark Mottian - 7 years, 6 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.)

Mark Mottian - 7 years, 6 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.

Oliver Welsh - 7 years, 6 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))

answer = 0
answer = (numerator/denominator)-1

print answer

Mark Mottian - 7 years, 6 months ago

@Mark Mottian – 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.

Ivan Koswara - 7 years, 6 months ago

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

Mark Mottian - 7 years, 6 months ago

@Ivan Koswara – Can u please answer some of my Questions in Programming?

Vamsi Krishna Appili - 7 years, 6 months ago

@Mark Mottian – Please , can u answer some of my questions in Programming.., I would start discussion a minute later please reply?

Vamsi Krishna Appili - 7 years, 6 months ago

@Vamsi Krishna Appili – The entire Brilliant community will try their best to answer your questions.

Mark Mottian - 7 years, 6 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!!

Mark Mottian - 7 years, 6 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

Piotr Kaminski - 7 years, 6 months ago

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

Mark Mottian - 7 years, 6 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

Task

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.

Mark Mottian - 7 years, 6 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)

Lee Gao - 7 years, 6 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.

Oliver Welsh - 7 years, 6 months ago

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

Ivan Koswara - 7 years, 6 months ago

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

Thaddeus Abiy - 7 years, 6 months ago

Algorithm Alert

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

Mark Mottian - 7 years, 6 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.

Ivan Koswara - 7 years, 6 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.

Edward Jiang - 7 years, 6 months ago

TASK!!!

Write programs to determine what is outlined above.

Mark Mottian - 7 years, 6 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

Mark Mottian - 7 years, 6 months ago

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

Project Euler

Priyanka Banerjee - 7 years, 6 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?

Mark Mottian - 7 years, 6 months ago

sorry

Hao Tian Lee - 7 years, 6 months ago

Math	Appears 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}$