Behöver hjälp med Kattis utmaning.... Virus replication

2018-05-12, 16:01 #1

Medlem

Reg: Mar 2008

Inlägg: 30

Såååå jag har suttit med de här testet ett par dagar men får inte till det helt och hållet. Kattis vill testa 13 olika samples för att kontrollera min kod och jag går igenom 8st sen blir något fel (jag kan inte se vad)

Här är länken till Kattis utmaningen: https://open.kattis.com/problems/virus

Vad är det jag missar? Vad är det för sample min kod inte kan läsa? blir lite smått galen.....
Hade vart jätte tacksam om någon kunde peka mig i rätt riktning eller hjälpa mig med ett svar <3

Kod:

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

namespace ConsoleApp3
{
    class Program
    {

        static void Main(string[] args)
        {
            Console.WriteLine(GetSample());
            Console.ReadKey();
        }

        public static int GetSample()
        {
            string sample1 = Console.ReadLine();
            string sample2 = Console.ReadLine();


            if (sample1 == sample2) return 0;

            if (sample1.Length >= sample2.Length)
            {
                for (int i = 0; i < sample2.Length; i++)
                {
                    if (!(sample1[i] == sample2[i]))
                    {
                        sample1 = sample1.Substring(i, sample1.Length - i);
                        sample2 = sample2.Substring(i, sample2.Length - i);
                        break;
                    }
                }

                int var = sample1.Length - sample2.Length;
                for (int i = sample2.Length - 1; i >= 0; i--)
                {
                    if (sample2[i] == sample1[i + var])
                        sample2 = trimlast(sample2);
                }
            }
            else
            {
                for (int i = 0; i < sample1.Length; i++)
                {
                    if (!(sample1[i] == sample2[i]))
                    {
                        sample1 = sample1.Substring(i, sample1.Length - i);
                        sample2 = sample2.Substring(i, sample2.Length - i);
                        break;

                    }
                }
                int var = sample2.Length - sample1.Length;
                for (int i = sample1.Length - 1; i >= 0; i--)
                {
                    if (sample2[i + var] == sample1[i])
                        sample2 = trimlast(sample2);
                }
            }
            return sample2.Length;

        }
        public static string trimlast(string str)
        {
            return str.Substring(0, str.Length - 1);
        }
    }

}

Citera

2018-05-13, 09:08 #2

Medlem

Reg: Jul 2017

Inlägg: 2 332

Det är inte bara så att programmet du skrivit tar för lång tid på sej? HackerRank kollar sånt. Gör Kattis detta? Isåfall kan du rikta in dej på att skriva om vissa delar som tar lång tid.
Strängarna kan ju vara upp till 10.000 tecken långa. Vet du om speciellt det fallet som failar tangerar max-gränsen?

Bara en idé...

Typ där du i en loop på 10 tusen gör sample1.Length 10 tusen gånger istället för att skapa en
int sampLen1 = sample1.Length;
bara en gång strax efter ReadLine och använda den istället inuti loopen.

__________________
Senast redigerad av MataRengi 2018-05-13 kl. 09:21.

Citera

2018-05-17, 09:21 #3

Medlem

Reg: Apr 2004

Inlägg: 2 627

Du gör det besvärligt för dig med allt substring-användande osv. Allt som behöver göras är att hitta var förändringen börjar från vänster och från höger:

Kod:


using System;



namespace KattisVirusReplication

{

    public class Program

    {

        static void Main(string[] args)

        {

            var clean = Console.ReadLine();

            var infected = Console.ReadLine();



            var result = FindLength(clean, infected);

            Console.WriteLine(result);

        }



        public static int FindLength(string clean, string infected)

        {

            var cl = clean.Length;

            var il = infected.Length;

            var minLength = Math.Min(cl, il);



            var leftDiff = minLength;

            var rightDiff = minLength;



            for (int i = 0; i < minLength; i++)

            {

                if (clean[i] != infected[i])

                {

                    leftDiff = i;

                    break;

                }

            }



            for (int i = 1; i <= minLength; i++)

            {

                if (clean[cl - i] != infected[il - i])

                {

                    rightDiff = i - 1;

                    break;

                }

            }



            var cleanRemaining = Math.Min(leftDiff + rightDiff, cl);

            var totalInserted = Math.Max(il - cleanRemaining, 0);



            return totalInserted;

        }

    }

}

Enhetstester (xunit):

Kod:


using KattisVirusReplication;

using Xunit;



namespace UnitTests

{

    public class DetectorTest

    {

        [Theory]

        [InlineData("AAAAA", "AGCGAA", 3)]

        [InlineData("GTTTGACACACATT", "GTTTGACCACAT", 4)]

        [InlineData("CAT", "CAT", 0)]

        [InlineData("", "CAT", 3)]

        [InlineData("CAT", "", 0)]

        [InlineData("", "", 0)]

        [InlineData("ab", "b", 0)]

        [InlineData("ab", "a", 0)]

        [InlineData("aaaabbbb", "abbbbb", 1)]

        [InlineData("ababab", "abab", 0)]

        public void FindLength(string clean, string infected, int length)

        {

            var result = Program.FindLength(clean, infected);



            Assert.Equal(length, result);

        }

    }

}

Citera

Behöver hjälp med Kattis utmaning.... Virus replication

Stöd Flashback