Coding challenge

stitchingStrings

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


//  Question:
//  We've taken some strings and chopped them up into pieces at random spots, then we're rearranged them and stuck them back together!
//  Your goal is to write some code that turns that process backwards.
//  We are going to provide you with an input file.
 
//  The first line is a comma-separated list of words that constitute the possible words in the string (the dictionary)
//  The second line is the scrambled input string
//  The third line is the number of splits we've made in the original string to get the scrambled version
 
//  Your program should output the unscrambled string (note: we promise there's only one solution for each example!). 
//  Examples:

//  Input:
//  hello
//  llohe
//  1
//  Output
//  hello

// Input:
// tarp,trap
// rapt
// 1
// Output:
// trap

namespace CodingChallenge
{
    public class Program
    {
        public static void Main(string[] args)
        {
            using(StreamReader sr = new StreamReader("input.txt"))
            {               
                char[] delimiters = {','};
                
                string input = sr.ReadLine();
                string[] allTheWords = input.Split(delimiters);
                
                string scrambledWord = sr.ReadLine();
                string normalizedScrambledWord = normalizeInput(scrambledWord);
                 
                string thirdInput = sr.ReadLine();
                int numOfCuts = Int32.Parse(thirdInput);
                 
                bool resultFound = false;
                foreach(var word in allTheWords) 
                {
                    string normalizedWord = normalizeInput(word);
                                        
                    var partitions = new List<string>();
                    
                    if(isMatch(normalizedWord, normalizedScrambledWord, numOfCuts, partitions)) {
                        Console.WriteLine("Output:");
                        Console.WriteLine(word);
                        resultFound = true;
                        break;
                    }
                }  
                
                if (!resultFound) {
                    Console.WriteLine("No matching word was found");    
                }
            }
        }
        
        static List<List<string>> getPermutations(List<string> input) {
            var result = new List<List<string>>();
            
            if (input.Count == 1) {
                result.Add(input);
                return result;
            }
            
            var first = input[0];
            
            var other = getPermutations(input.Skip(1).ToList());
            
            foreach(var item in other) {
                for(int i = 0; i <= item.Count; i++) {
                    var current = new List<string>(item);
                    current.Insert(i, first);
                    result.Add(current);
                }
            }
            
            return result;
        }
       
        static bool isMatch(string unscrambledWord, 
            string scrambledWord, 
            int cuts, 
            List<string> partitions) {
            
            Console.WriteLine("Unscrambled: {0}, Scrambled: {1}, Cuts: {2}, Number of partitions: {3}", 
                unscrambledWord, 
                scrambledWord, 
                cuts,
                partitions.Count);
            
            if (cuts == 0) {
                partitions.Add(unscrambledWord);
                
                var permutations = getPermutations(partitions);
                
                foreach(var item in permutations) {
                    var candidate = String.Join("", item);
                    if (candidate.CompareTo(scrambledWord) == 0) {
                        return true;
                    }
                }
                
                partitions.RemoveAt(partitions.Count - 1);
                
                return false;
            }
            
            int reducedCuts = cuts - 1;
            for(int i = 0; i <= unscrambledWord.Length - 1 - cuts; i++) {
                var currentPartition = unscrambledWord.Substring(0, i + 1);
                partitions.Add(currentPartition);
                if (isMatch(unscrambledWord.Substring(i + 1), scrambledWord, reducedCuts, partitions)) {
                    return true;
                }
                partitions.RemoveAt(partitions.Count - 1);
            }           
            
            return false;
        } 
       
        static string normalizeInput(string s) 
        {
            s = s.Trim();
            return s.ToLower();
        }
    }
}

test!!