Posts Tagged with "Combinatorics"

6988272680_8146a984c3_o

Project Euler 267: Billionaire

Sunday, February 9, 2014

6 Comments

It has been a long while since I solved any Project Euler problem. For some reason I read an article about it and someone references Problem 267, so I decided to take a look at it, and it sucked me in. The problem reads You are given a unique investment opportunity. Starting with £1 of […]

Continue reading...
featured

Project Euler 121: Investigate the game of chance involving coloured discs

Saturday, November 3, 2012

5 Comments

To be honest, problem 121 of Project Euler scared me a whole lot, since my probability theory is not very strong. However, I do believe that I came up with quite a nice solution after all. The problem readsA bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its colour is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played. At first I tried to solve it by making Monte Carlo simulations, but I kept getting different results. Which shows me that I would need to go very far up in the number of simulations. And that in turn took a long time. So I had to find another approach.

Continue reading...
6a00d83451626369e200e553d8a36f8834

Project Euler 118: Exploring the number of ways in which sets containing prime elements can be made.

Saturday, October 13, 2012

3 Comments

Problem 118 have a very short problem description which in all it's glory readsUsing all of the digits 1 through 9 and concatenating them freely to form decimal integers, different sets can be formed. Interestingly with the set {2,5,47,89,631}, all of the elements belonging to it are prime.How many distinct sets containing each of the digits one through nine exactly once contain only prime elements?I see two approaches to this problem of which I have taken one of them. The first solution approach which I have taken is to generate all permutations of the digits 1-9 and then check if you can split them in to ordered sets of primes.

Continue reading...
278624764_e935d75f1b_o

Project Euler 113: How many numbers below a googol (10^100) are not “bouncy”?

Friday, September 7, 2012

2 Comments

In Problem 112 of Project Euler we got an introduction to bouncy numbers. In Problem 113 we will revisit this concept and solve the problem Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468. Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420. We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349. How many numbers below a googol (10100) are not bouncy?Many have written that this problem can be solved using lattice paths. However, if you have no real clue what a lattice is, this doesn't really help you to fully understand the problem . I had an idea that was the right path and fiddled with the problem until I got the right answer. Later on I have found a much better explanation for why the combinatorics solution is correct.

Continue reading...
sets

Project Euler 106: Find the minimum number of comparisons needed to identify special sum sets.

Saturday, July 21, 2012

6 Comments

Unlike Problem 105 which I wasn't too impressed with Problem 106 of Project Euler has really lead me to gain some insights into the special sum sets. The problem readsSurprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?Let me warn you upfront that this will be a rather long post, as it will detail many of the insights I got while fiddling around with this problem in order to understand it. If this hasn't scared you away I will suggest that you go pick up a cup of tea or coffee and settle down for the ride.

Continue reading...
sets

Project Euler 105: Find the sum of the special sum sets in the file.

Saturday, July 14, 2012

0 Comments

Problem 105 of Project Euler is closely related to Problem 103 as has been mentioned in both problem descriptions. The problem formulation for this problem isidentify all the special sum sets, A1, A2, ..., Ak, and find the value of S(A1) + S(A2) + ... + S(Ak).To be completly honest, I haven't gotten all that many new insights from solving this problem compared to Problem 103. What we need here is to check if a set of numbers fulfils both properties. In problem 103 we generated specific functions for checking each of the properties, so I have just reused these functions in order to solve this problem. ​I did discover a bug in Problem 103 when I solved this, but that has been corrected now, so I did get something from the problem but not much.

Continue reading...
sets

Project Euler 103: Investigating sets with a special subset sum property.

Saturday, June 30, 2012

4 Comments

Problem 103 of Project Euler is a hard problem if we look at the amount of people who solved it. And I tend to agree, it took me a while to solve it. The problem readsLet S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:S(B) ≠ S(C); that is, sums of subsets cannot be equal. If B contains more elements than C then S(B) > S(C).If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below. Given that A is an optimum special sum set for n = 7, find its set string.Before starting on deriving a solution I would like to say that I made a solution using brute force, a really ugly solution. So when I saw another solution I borrowed the majority of it and made some modifications to it in order to speed it up a bit. So if the coding style is not exactly the same as I usually present this is the probably the reason. But lets get started...

Continue reading...
arithmetic

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

Saturday, April 21, 2012

24 Comments

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 readsFind 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. As I mentioned in the beginning, I have only been able to solve this using brute force. That being said there are several interesting aspects on how to cover the whole search space for the best solution.

Continue reading...
89

Project Euler 92: Investigating a square digits number chain with a surprising property.

Saturday, April 14, 2012

7 Comments

Problem 92 of Project Euler is one of the more solve puzzles in this range, so based on that parameter this should be a pretty easy thing to chew through. The problem text reads A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. How many starting numbers below ten million will arrive at 89? I have found two methods to solve this. One where we go through all 10.000.000 numbers to check what their cycle will be with a bit of help from some caching. And then a method where we exploit the fact that the order of the digits doesn't matter and that significantly reduces the cases we need to check.

Continue reading...
dice

Project Euler 90: An unexpected way of using two cubes to make a square.

Saturday, March 31, 2012

8 Comments

In the ninetieth problem of Project Euler we are back in combinatorics with a problem description that readsHow many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?This problem can be solved brute forcing all combinations of dices since the solution space is not that big. But before going on solving the problem lets have a look at how many potential solutions we have.

Continue reading...