fork download
copy 
  1. using System;
  2. using System.Text.RegularExpressions;
  3. using System.Collections.Generic;
  4. using System.Linq;
  5.  
  6. class Program
  7. {
  8.     // The maximum number of characters we are willing to remove to achieve a match.
  9.     // Set this based on the expected level of corruption. Higher numbers mean exponentially longer runtimes.
  10.     const int MaxDeletions = 3; 
  11.  
  12.     // The target regex pattern for a valid date/time string.
  13.     static readonly string Pattern = @"^\d{2}/\d{2}/\d{2} \d{2}:\d{2}:\d{2}$";
  14.  
  15.     static void Main()
  16.     {
  17.         // Test cases:
  18.         // 1. Valid
  19.         // 2. 1 rogue char at start (X)
  20.         // 3. 1 rogue char in middle (X)
  21.         // 4. 2 rogue chars (Y and Z)
  22.         // 5. Corruption (missing separator) - should fail gracefully
  23.  
  24.         string[] testInputs =
  25.         {
  26.             "11/10/25 17:22:31",        
  27.             "X11/10/25 17:22:31",       
  28.             "11/10/25 Y17:22:31Z",      
  29.             "Y11/10/25 Z17:22:31",
  30.             "1110/25 17:22:31",         
  31.             "A B C D 11/10/25 17:22:31" // 4 rogue chars - should hit MaxDeletions limit (3)
  32.         };
  33.  
  34.         foreach (string input in testInputs)
  35.         {
  36.             Console.WriteLine(new string('-', 50));
  37.             Console.WriteLine($"Testing Input: \"{input}\"");
  38.  
  39.             if (Regex.IsMatch(input, Pattern))
  40.             {
  41.                 Console.WriteLine("Result: Matches the pattern (0 deletions required).");
  42.             }
  43.             else
  44.             {
  45.                 Console.WriteLine($"Result: Does NOT match. Searching for minimum deletions (max {MaxDeletions})...");
  46.                 FindMinimalRogueChars(input);
  47.             }
  48.         }
  49.     }
  50.  
  51.     /// <summary>
  52.     /// Searches for the minimal set of characters (up to MaxDeletions) whose removal makes the input match the pattern.
  53.     /// </summary>
  54.     static void FindMinimalRogueChars(string input)
  55.     {
  56.         // We look for solutions iteratively starting from 1 deletion up to MaxDeletions.
  57.         // This ensures the first solution found is the minimal one.
  58.         for (int k = 1; k <= MaxDeletions; k++)
  59.         {
  60.             // The recursive helper function is called to find all combinations of 'k' deletions.
  61.             var rogueIndices = new List<int>();
  62.  
  63.             // If the recursive search finds a match at this depth 'k', we stop immediately.
  64.             if (FindAndCheck(input, Pattern, k, 0, rogueIndices))
  65.             {
  66.                 // Format the output list
  67.                 var removedChars = rogueIndices.Select(i => $"'{input[i]}' at index {i}").ToList();
  68.                 var validString = new string(input.Where((c, i) => !rogueIndices.Contains(i)).ToArray());
  69.  
  70.                 Console.WriteLine($"✅ SUCCESS: Found solution requiring {k} deletion(s).");
  71.                 Console.WriteLine($"   Rogue Characters: {string.Join(", ", removedChars)}");
  72.                 Console.WriteLine($"   Valid String: \"{validString}\"");
  73.                 return; // Stop searching (since k is minimal)
  74.             }
  75.         }
  76.  
  77.         // If the loop finishes without returning, no minimal solution was found within MaxDeletions.
  78.         Console.WriteLine($"❌ FAILURE: No valid solution found by removing {MaxDeletions} or fewer characters.");
  79.     }
  80.  
  81.     /// <summary>
  82.     /// Recursive backtracking function to try all combinations of 'k' deletions.
  83.     /// </summary>
  84.     /// <param name="input">The original input string.</param>
  85.     /// <param name="pattern">The regex pattern.</param>
  86.     /// <param name="deletionsLeft">The number of characters still allowed to be removed.</param>
  87.     /// <param name="startIndex">The index in the input string to start looking for the next character to remove (to avoid duplicate combinations).</param>
  88.     /// <param name="currentRogues">A list tracking the indices of characters removed so far.</param>
  89.     /// <returns>True if a match is found, false otherwise.</returns>
  90.     static bool FindAndCheck(
  91.         string input, 
  92.         string pattern, 
  93.         int deletionsLeft, 
  94.         int startIndex, 
  95.         List<int> currentRogues)
  96.     {
  97.         // 1. Base Case: No more deletions allowed.
  98.         if (deletionsLeft == 0)
  99.         {
  100.             // Construct the resulting string by omitting all characters marked in currentRogues.
  101.             var testString = new string(input.Where((c, i) => !currentRogues.Contains(i)).ToArray());
  102.  
  103.             // Check if the resulting string matches the pattern
  104.             return Regex.IsMatch(testString, pattern);
  105.         }
  106.  
  107.         // 2. Recursive Step: Try removing the next character.
  108.         // The loop condition ensures we have enough remaining characters in the input
  109.         // to select the remaining number of characters to delete.
  110.         for (int i = startIndex; 
  111.              i < input.Length - deletionsLeft + 1; 
  112.              i++)
  113.         {
  114.             // ACTION: Remove the character at index 'i' (by adding its index to the list)
  115.             currentRogues.Add(i);
  116.  
  117.             // RECURSE: Move to the next depth, requiring one less deletion, 
  118.             // and start the search from the next index (i + 1) to ensure we only move forward 
  119.             // and get unique combinations.
  120.             if (FindAndCheck(input, pattern, deletionsLeft - 1, i + 1, currentRogues))
  121.             {
  122.                 return true; // Found a solution at this combination
  123.             }
  124.  
  125.             // BACKTRACK: If the recursive call failed to find a match, 
  126.             // undo the removal before trying the next character in the loop.
  127.             currentRogues.RemoveAt(currentRogues.Count - 1);
  128.         }
  129.  
  130.         return false;
  131.     }
  132. }
  133.  
Success #stdin #stdout 0.12s 33988KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
--------------------------------------------------
Testing Input: "11/10/25 17:22:31"
Result: Matches the pattern (0 deletions required).
--------------------------------------------------
Testing Input: "X11/10/25 17:22:31"
Result: Does NOT match. Searching for minimum deletions (max 3)...
✅ SUCCESS: Found solution requiring 1 deletion(s).
   Rogue Characters: 'X' at index 0
   Valid String: "11/10/25 17:22:31"
--------------------------------------------------
Testing Input: "11/10/25 Y17:22:31Z"
Result: Does NOT match. Searching for minimum deletions (max 3)...
✅ SUCCESS: Found solution requiring 2 deletion(s).
   Rogue Characters: 'Y' at index 9, 'Z' at index 18
   Valid String: "11/10/25 17:22:31"
--------------------------------------------------
Testing Input: "Y11/10/25 Z17:22:31"
Result: Does NOT match. Searching for minimum deletions (max 3)...
✅ SUCCESS: Found solution requiring 2 deletion(s).
   Rogue Characters: 'Y' at index 0, 'Z' at index 10
   Valid String: "11/10/25 17:22:31"
--------------------------------------------------
Testing Input: "1110/25 17:22:31"
Result: Does NOT match. Searching for minimum deletions (max 3)...
❌ FAILURE: No valid solution found by removing 3 or fewer characters.
--------------------------------------------------
Testing Input: "A B C D 11/10/25 17:22:31"
Result: Does NOT match. Searching for minimum deletions (max 3)...
❌ FAILURE: No valid solution found by removing 3 or fewer characters.
https://ideone.com/zczD7J
language:
C# (NET 6.0)
created:
5 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!