C# програмиране - част I - Problem 5 – Neuron Mapping - Изпит на 23.06.2013

Задача 1
Задача 2
Задача 3
Задача 4
Задача 5

Здравейте,

Ето че стигнахме до битовата задача.

Условието на задачата може да изтеглите от тук: 5. Neurons.doc

Тази задача я правих 2 пъти from scratch.
Питате се защо ли? Ами причината ще я разберете по-надолу.

Първо ми хрумна следния алгоритъм:
Обръщам всички 0 на 1 и обратно. След което изчиствам рекурсивно всички 1 които се допират до стените, техните съседи и така докато стигна до 0 (достигнатите нули са точно ограждането на някой neuron, които от 1 са станали 0 при обръщането, и по този начин вътрешните не ги докосвам.
Логиката е чудесна и работи за примерите.
Ето и кода:

using System;
using System.Collections.Generic;

class NeuronMapping
{
    static void ClearAtPosition(List input, int x, int y)
    {
        if (x >= 0 && x < 32 && y >= 0 && y < input.Count)
        {
            if ((input[y] & (1 << x)) != 0)
            {
                input[y] = input[y] & (~((uint)1 << x));
                ClearAtPosition(input, x - 1, y);
                ClearAtPosition(input, x + 1, y);
                ClearAtPosition(input, x, y - 1);
                ClearAtPosition(input, x, y + 1);
            }
        }
    }

    static void Main()
    {
        List input = new List();
        while (true)
        {
            string inString = Console.ReadLine();
            if (inString == "-1")
            {
                break;
            }
            uint number = uint.Parse(inString);
            input.Add(~number);
        }
        for (int x = 0; x < 32; x++)
        {
            ClearAtPosition(input, x, 0);
            ClearAtPosition(input, x, input.Count - 1);
        }
        for (int y = 0; y < input.Count; y++)
        {
            ClearAtPosition(input, 0, y);
            ClearAtPosition(input, 31, y);
        }
        foreach (var item in input)
        {
            Console.WriteLine(item);
        }
    }
}

Но се оказа че не покрива 100% от тестовете в bgcoder. Един от тях даваше грешен отговор. От тук на сетне започна голямото чудене зато е така.
Чудех се можеше ли да остане поле между neuron-ите което да не изчиствам. Какви ли не мисли ми минаха през главата.

Накрая реших да започна отначало цялата програма с нов алгоритъм. А именно, за всеки ред първо обръщам с побитова операция НЕ (~), след това от двата края всички единици ги правя от 1 на 0 до срещане на 0.
Този алгоритъм ми докара 100%.

Ето и кода:

using System;
using System.Collections.Generic;

class NeuronMapping2
{
    static void Main()
    {
        List input = new List();
        while (true)
        {
            string inString = Console.ReadLine();
            if (inString == "-1")
            {
                break;
            }
            uint number = uint.Parse(inString);
            number = ~number;
            for (int i = 0; i < 32; i++)
            {
                if ((number & (1 << i)) != 0)
                {
                    number = number & (~((uint)1 << i));
                }
                else
                {
                    break;
                }
            }
            for (int i = 31; i >= 0; i--)
            {
                if ((number & (1 << i)) != 0)
                {
                    number = number & (~((uint)1 << i));
                }
                else
                {
                    break;
                }
            }
            input.Add(number);
        }
        foreach (var item in input)
        {
            Console.WriteLine(item);
        }
    }
}

На пръв поглед ползването на "сложната" рекурсия може да е причината. Но аз не мисля така. Във втория алгоритъм има логически бъг въпреки че ми прави 100%.
Нека да разгледаме следния пример:

................................ 0
.....................11....11... 1560
....................1..1..1..1.. 2340
...................1....11....1. 4290
....................1........1.. 2052
.....................1......1... 1032
......................1....1.... 528
.......................1..1..... 288
........................11...... 192
................................ 0

Този вход би трябвало да ми даде следния изход, ако правилно съм разбрал условието (не го твърдя, нямам претенции английския да ми е перфектен):

................................ 0
................................ 0
.....................11....11... 1560
....................1111..1111.. 3900
.....................11111111... 2040
......................111111.... 1008
.......................1111..... 480
........................11...... 192
................................ 0
................................ 0

И точно това е резултата с първия алгоритъм.
А със втория резултата е:

................................ 0
.......................1111..... 480
.....................11.11.11... 1752
....................1111..1111.. 3900
.....................11111111... 2040
......................111111.... 1008
.......................1111..... 480
........................11...... 192
................................ 0
................................ 0

Но пък той ми донесе 100%


Хареса ми преживяването имаше емоция, трудности, проблеми за решаване. Удоволствието е невероятно, ако се сблъскаш с трудности и накрая успееш да се справиш.

И благодаря за времето което отделихте да прочетете преживяванията ми по време на изпита.