Algorithms

xx77abs wrote:

And one more thought ... Should I try placing every rectangle two times(normal and 90 degrees rotated) in the big rectangle and use memoization? Then I can determine how must small rectangles can there be for that algorithm to be executing in about 10 seconds ?

xx77abs wrote:

And I also have one more problem ... What's the best way to remember what parts of big rectangle I've already used ? I don't know how to do it ... Should I try with some custom class or ?? Please tell me if you have any ideas

harold aptroot wrote:

I don't really know what you mean by that - could you explain it in more detail?

harold aptroot wrote:

I have a couple of idea, but none of them are really good:
1) directly use the positions of the rectangles to calculate intersections (slow)
2) use a bitarray (too much memory)
3) hybrid: store big rectangles as rectangles, but use bitarrays to store the small rectangles (justification: in general the small rectangles will end up close to each other since using small rectangles leaves small gaps) Very complex though, and it may not be worth the effort

You're welcome, but I have the nagging feeling that there is a better solution - I just don't know what it is.

1. read all text into a single string (File.ReadAllText)

2. have a main loop traversing the text, and get the substring with length 2

3. now call recursive method that uses String.IndexOf to locate and count extra occurences of that substring

4. when found, for each of them increase substring length by 1 and recurse to 3

khalidelmeknesi wrote:

an example?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string _givenString = "wvtnfhxyz1hdxyz1fdxyz1ejxyz1dhxyz1dxyz1eeaa1oeys";
            Dictionary<string, int> _codes = new Dictionary<string, int>();
            int _startingPoint = 0;
            while (_startingPoint < _givenString.Length)
            {
                for (int j = 2; j < _givenString.Length; j++)
                {
                    for (int i = _startingPoint; i < _givenString.Length && i + j < _givenString.Length; i++)
                    {
                        if (!_codes.ContainsKey(_givenString.Substring(i, j)))
                        {
                            _codes.Add(_givenString.Substring(i, j), 1);
                        }
                        else
                        {
                            _codes[_givenString.Substring(i, j)] += 1;
                        }
                    }
                }
                
                _startingPoint++;
            }

            List<KeyValuePair<string, int>> _sortedCodes = SortDictionary(_codes);
            for (int i = 0; i < 5; i++)
            {
                Console.WriteLine(_sortedCodes[i].Key + " : " + _sortedCodes[i].Value + " times");
            }
            Console.ReadKey();
        }

        public static List<KeyValuePair<string, int>> SortDictionary(Dictionary<string, int> data)
        {
            List<KeyValuePair<string, int>> result =
                  new List<KeyValuePair<string, int>>(data);
            result.Sort(
              delegate(
                KeyValuePair<string, int> first,
                KeyValuePair<string, int> second)
              {
                  return second.Value.CompareTo(first.Value);
              }
              );
            return result;
        }
    }
}