String Manipulation

Project Euler 89: Develop a method to express Roman numerals in minimal form.

Project Euler 89: Develop a method to express Roman numerals in minimal form.

I feared that the problems would become harder and harder, and after solving problem 88 I feared Problem 89 of Project Euler. Luckily for me I was wrong, problem 89 is not that difficult. The problem reads

The rules for writing Roman numerals allow for many ways of writing each number (see About Roman Numerals…). However, there is always a “best” way of writing a particular number.

For example, the following represent all of the legitimate ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

The last example being considered the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt  contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; that is, they are arranged in descending units and obey the subtractive pair rule (see About Roman Numerals… for the definitive rules for this problem).

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

Continue reading →

Posted by Kristian in Project Euler, 9 comments

Project Euler 42: How many triangle words does the list of common English words contain?

Problem 42 of Project Euler presents us with a new string manipulation problem. The problem asks us the following

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Continue reading →

Posted by Kristian in Project Euler, 8 comments

Project Euler 36: Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2

In Problem 36 of Project Euler we are revisiting palindromic numbers. This time with we need to find numbers which are not only palindromic in base 10 but also in base two, meaning in a binary representation. The problem description reads

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Continue reading →

Posted by Kristian in Project Euler, 14 comments

Project Euler 22: What is the total of all the name scores in the file of first names?

Project Euler has a large variety in the sort of problems they pose. Problem 22, as we will solve now, has nothing to do with mathematics and everything to do with computer science and sorting algorithms. The problem reads

Using names.txt (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 x 53 = 49714.

What is the total of all the name scores in the file?

The way I want to solve this problem, is to split it into three parts

  1. Read the input file and turn the data into a manageable data structure
  2. Sort the data
  3. Sum up and provide the answer

Continue reading →

Posted by Kristian in Project Euler, 20 comments