Cumulative Programming Contest

[Sirp]

I noticed the thread on the computer trivia quiz, and thought it was a good idea - so I'm starting this similiar thread.

Essentially, we want questions/puzzles that would be difficult for a human to solve by hand, but are conducive to computer-based or programatic solutions. The first person to give the correct answer gets to make the next puzzle. Discussing possible solutions and ideas is encouraged. One doesn't have to use a computer or programming to answer a question, but if the question is well-designed that's probably going to be the easiest way to do it.

Questions should probably be solvable on a low-end machine. Someone will be considered to have gotten the correct answer if they can post a proof as to why the question is impossible to solve easily, or at all.

Posters are also encouraged to post solutions to problems in various languages, including perhaps, weird and whacky solutions, terse solutions, and very elegant solutions.

I'll kick it off with the first problem in my first post.

 

[Sirp]

ok, here is the first puzzle (and yes, I copied the idea for this puzzle from elsewhere...):

An "addagram" is a sequence of words: beginning with a 3-letter word, one adds a letter, rearranges the 4 letters one now has, to form a new word. Then another letter is added, and the letters are rearranged again to form yet another word.

For instance:

mar
mar + c = cram
cram + h = march
march + s = charms

and so on.

The aim of the puzzle is to find the longest possible sequence that can be formed in english.

If you don't have an electronic dictionary to use as a data set to solve this problem, you can get one from: http://www.itasoftware.com/careers/WORD.LST

It's just a flat file, one word per line.

(note that if people use different dictionaries , slightly different results might arise, but I'm sure we can handle that)

 

[Mechanical_Animal]

When creating addagrams, how should the next word be chosen if there are multiple words to create

eg.
race + t = trace
race + s = races

should we choose arbitrarily (doesn't matter which one is chosen, as long as one is) or is there a definite rule for which one should be added (for example races would be used since 's' comes before 't').

Arbitrarily choosing makes it a lot easier to code.
Or should all possibilities be considered???

Also for those who don't speak english, if you get a words file in your language, you can still participate. Your results however will be different.

 

[Sirp]

Sorry, maybe I didn't explain it well enough. You can choose any addagram sequence you like. So if there are multiple possible words, you can choose whichever one you like.

Also, people can use non-english dictionaries if they want, although they are encouraged to use the dictionary to which a reference was posted. (they could perhaps develop their solution using a dictionary in their native language, but then switch over to use the referenced dictionary with their final solution so that they can compare their solution with others).

 

[Mechanical_Animal]

The problem is solveable, however from what's happened to me already finding a solution will probably take a large amount of time.

An easier and quicker sub problem might be to find all the possible words that can be created by adding one letter to an existing word.
eg. given car the program would find
car + b = crab
car + d = card
car + e = acre
car + e = care
car + e = race

If you can't solve the problem or its taking too long, try this one.

 

[Sirp]

The problem seems pretty hard at first, but once you think about it for a while, you'll probably be able to work out an answer without too much trouble. (depending upon your programming experience, aptitude for this kind of thing, and so forth )

I have a solution to it written in about 50 lines of C++.

hmm...perhaps I should have started things off with a slightly easier question...I'll post an easier problem if there are no promising looking answers to this one anytime soon.

 

[Lovro]

Off the top of my head...

• Since we're dealing with anagrams, sort each word independently of each other in increasing alphabetic order (thus, "march" becomes "archm").
• Next, sort all the words in alphabetically increasing order
• The solution is the longest sequence of words such that the i-th word is the prefix of the i+1th word, and the i+1th word is exactly one character longer than the i-th word.

Now for the complexity.

• Sorting every word will symptotically be fastest done in quadratic time using insertion sort
• Sorting the entire file will be easiest done using quicksort with strcmp
• Finding the actual longest sequence can be done in time linear to the number of words in the file

Just coded this, and it says '18' for the dictionary you supplied, Sirp. Is this correct?

EDIT: This algorithm is wrong. While it solves another problem efficiently, it does not solve this one at all.

 

[Sirp]

Lovro: I'm afraid I'm at work at the moment, and don't have my result to check against. Anyhow, the aim of the puzzle was to give the complete addagram sequence, not just tell us how long it is!

I'd imagine that'd be a little more work, but not too much...

anyhow, your solution is sound...

 

[Lovro]

Anyway, I noticed my solution was wrong anyway (misread the problem description), but making another one should not be hard.

EDIT: The maximum sequence I found is of length 11 and consists of the following words:

no
nor
nori
irone
orient
orients
serotine
stereoing
estrogenic
egocentrism
egocentrisms

Is this correct (the length, the sequence itself needs not be unique)?

 

[Sirp]

Lovro:

I got a longer sequence than you for my answer. It is:

inn
nine
inane
eonian
enation
sonatine
antinoise
antinomies
nitrosamine
terminations
antimodernist
determinations
intermediations
indeterminations

I would like to know why we got different answers though your proposed solution did seem sound; and I think mine is too.

I have attached the source code to my solution (in C++) if you're interested. I used a slightly different approach in that I started with the largest words, and tried to find a sequence backwards, as I reasoned that it would be faster this way.

You can post the next puzzle, since you're the only one to come up with anything looking like a solution...

 

[Lovro]

Oh, yet again did I not solve the correct problem. My solution (the sequence of 11 words) works so that you rearrange the current word and then add an arbitrary latter to the end of the rearranged word to form another word... The algorithm that generates this solution also goes from the last word in a dynamic way.

Well, good enough for me.

I will be posting the next question later today.

 

[Lovro]

This problem is somewhat easier than the previous, as you will see below. It also has more of an educational feeling to it.

-----------------------------------
Given a natural number N as input, generate all quadruples of natural numbers smaller than or equal to (<=) N such that

A^2 + B^2 + C^2 = D^2

Some of these include (1, 2, 2, 3), (1, 4, 8, 9) and (2, 3, 6, 7).

In this problem, you only need to enumerate all such quadruples, not output all of them.

Sequences such as (1, 2, 2, 3) and (2, 1, 2, 3) should only be counted once, i.e. all triplets (A, B, C) need to be unique.

For example, there is only one such quadruple when N=5, and six when N=10.
-----------------------------------

I will be absent and not able to validate any solutions, I recommend you try and see how large of an N your program can solve the problem for in reasonable time (say, less than ten seconds). The person (other than Sirp) with the largest N (best algorithm) wins.

To check the correctness of your program, see http://www.civfanatics.net/uploads/problem2_solution.txt. This textfile also outlines four different methods of solving, each faster than the previous one and shows how each one evolves from the previous ones.

 

[ainwood]

I haven't had a (serious) try at this yet, but a couple of observations:

1.) From the sample code, calculating (A*A + B*B + C*C) in the inner-most loop is inefficient. You should calculate A*A and store it for each A iteration; ditto for B*B and C*C. Then just compare the sums each term. You can go further, by storing SqrA + SqrB for each iteration etc.

2.) Noting the point that A<=B<=C, there is no point in iterating for any A² > N²/3

3.) In assessing the algorithms "Efficiency", how do you assess them on comparitive programming languages / platforms?

 

[Sirp]

ainwood: algorithms are easily compared independently of language and platform. Essentially, in most cases the important thing about an algorithm is its performance when the input data becomes very large. Does it take the same amount of time, independent of how much input data there is? Does it increase in time linearly? Exponentially?

What's generally used to assess how efficient an algorithm is is generally known as "O-notation". We say an algorithm is O(n) if it increases linearly when the data set becomes large. It's O(log(n)) if it increases logarithmically, and so forth. Do a search on google for it, and you will find plenty of far more detailed explanations.

 

[gonzo_for_civ]

This thread has not received replies in many days so I am going to un-sticky it. It will remain in this forum and open though so don't take this as a thread closure.