Permutations

UVa 102: Ecological Bin Packing

UVa 102: Ecological Bin Packing

We’re back to doing another simple UVa Online Judge problem, and this time we take on problem 102, Ecological Bin Packing. In the problem we are asked to solve a bin packing problem about recycling glass. It can be easily solved with brute force, but requires careful coding. Enough yapping, let’s take a look at the problem description.

Interpretation

We have three bins, each of which contains some number of bottles. There are three types of bottles; brown, green and clear, denoted by “B”, “G” and “C”, respectively. We are given how many  bottles of each type are in each bin. Continue reading →

Posted by Bjarki Ágúst in UVa Online Judge, 1 comment
Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

Project Euler 93: Using four distinct digits and the rules of arithmetic, find the longest sequence of target numbers.

I really start feeling that the problems become more and more difficult. Problem 93 of Project Euler was not trivial at all. And as we shall see the only solution I found was a brute force solution.  The problem reads

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) – 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

Continue reading →

Posted by Kristian in Project Euler, 31 comments
Project Euler 68: What is the maximum 16-digit string for a “magic” 5-gon ring?

Project Euler 68: What is the maximum 16-digit string for a “magic” 5-gon ring?

We have now been dealing with continued fractions for a good while, except for the last problem which was solved a good while ago. Problem 68 of Project Euler is completely different. It reads

Consider the following “magic” 3-gon ring, filled with the numbers 1 to 6, and each line adding to nine.

Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

Total Solution Set
9 4,2,3; 5,3,1; 6,1,2
9 4,3,2; 6,2,1; 5,1,3
10 2,3,5; 4,5,1; 6,1,3
10 2,5,3; 6,3,1; 4,1,5
11 1,4,6; 3,6,2; 5,2,4
11 1,6,4; 5,4,2; 3,2,6
12 1,5,6; 2,6,4; 3,4,5
12 1,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a “magic” 5-gon ring?

Well we could try to pursue a brute force approach but we have 10! = 3628800 combinations to check. An approach I will take in the end of this post. However, we can see if we can solve it by hand. So let’s try greedy algorithm using pen & paper. Continue reading →

Posted by Kristian in Project Euler, 14 comments
Project Euler 62: Find the smallest cube for which exactly five permutations of its digits are cube

Project Euler 62: Find the smallest cube for which exactly five permutations of its digits are cube

Problem 62 of Project Euler goes

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

Continue reading →

Posted by Kristian in Project Euler, 7 comments
Project Euler 52: Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order

Project Euler 52: Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order

Problem 52 of Project Euler reads

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Between solving this problem and writing this text I did a bit of research on other peoples solutions. It seems that some people already knew the answer from an old high school exercise with fractions or from the book The man who counted by Malba Tahan. The book cover of that book is used for this posts headline image. I must admit that I didn’t know that. Apparently I could have just asked Wikipedia for the answer.

So based on my apparently limited knowledge on this problem I went for the brute force solution. Continue reading →

Posted by Kristian in Project Euler, 8 comments
Project Euler 49: Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other

Project Euler 49: Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other

Problem 49 of Project Euler asks us to find three numbers with the following properties

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

When I first read the description I misread the description and interpreted it as I had to find a sequence which was 3330 apart. So I solved that problem and arrived with a correct solution. However, I realise this was not what was meant with the problem.  So the solution I will present here is one that looks for any three number sequence with equal distance among two neighbouring terms and having properties (i) and (ii). Continue reading →

Posted by Kristian in Project Euler, 28 comments

Project Euler 43: Find the sum of all pandigital numbers with an unusual sub-string divisibility property

When I first saw pandigital numbers I thought it was just a curious thing that we would visit once. I was wrong as Problem 42 of Project Euler is also about a special group of pandigital numbers. The problem reads

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

We will take two different approaches to this. First We will explore the brute force of generating all permutations and after that we will use the divisibility requirements to limit the number of permutations we have to explore. Continue reading →

Posted by Kristian in Project Euler, 18 comments

Project Euler 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Problem 24 of Project Euler is about permutations, which is in the field of combinatorics. The posed question is as follows

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

There is a clever way to solve it, and a brute force solution. Since the brute force algorithm still requires some thought on how to generate permutation, I will cover both methods in this post. Continue reading →

Posted by Kristian in Project Euler, 38 comments