Single Letter Swaps (Code Challenge)
- Page Owner: Not Set
- Last Reviewed: 2019-09-06
I dropped down to the "very hard" puzzles to hopefully make this less time consuming and more fun. Enjoy!
Single Letter Swaps
Given an array of strings and an original string, write a function to output an array of boolean values
- Return true if the word can be formed from the original word by swapping two letters only once
- Return false if the the word cannot be formed, or it would require more than two swaps
Examples
validateSwaps(["BACDE", "EBCDA", "BCDEA", "ACBED"], "ABCDE")
➞ [true, true, false, false]
// Swap "A" and "B" from "ABCDE" to get "BACDE".
// Swap "A" and "E" from "ABCDE" to get "EBCDA".
// Both "BCDEA" and "ACBED" cannot be formed from "ABCDE" using only a single swap.
validateSwaps(["32145", "12354", "15342", "12543"], "12345")
➞ [true, true, true, true]
validateSwaps(["9786", "9788", "97865", "7689"], "9768")
➞ [true, false, false, false]
Notes
- Original string will consist of unique characters.
Tests
validateSwaps(['BACDE', 'EBCDA', 'BCDEA', 'ACBED'], 'ABCDE'),[true, true, false, false]
validateSwaps(['32145', '12354', '15342', '12543'], '12345'),[true, true, true, true]
validateSwaps(['9786', '9788', '97865', '7689'], '9768'),[true, false, false, false]
validateSwaps(['123', '321', '132', '13', '12'], '213'), [true, false, false, false, false]
validateSwaps(['123', '1234', '1235'], '12'), [false, false, false]
validateSwaps(['123', '123', '123'], '133'), [false, false, false]
validateSwaps(['132', '321', '213'], '123'), [true, true, true]
Additional Posts
Boom. The perfect answer. These is no better way to do this.
function getRandomInt(max) {
return Math.floor(Math.random() * Math.floor(max));
}
function checkSwaps(left, right) {
// First, figure out all possible swap possibilities.
// Store that in the format of X,Y, where x and y are the indices to swap.
var all_possible_combinations = [];
// Algorithm: pick indicies at random to add to the list. Do this until all possible
// combinations are found.
let attempts = 0;
while (all_possible_combinations.length < (left.length * left.length)) {
let x = 0;
let y = 0;
let combined = `${x},${y}`;
while (all_possible_combinations.indexOf(combined) >= 0) {
x = getRandomInt(left.length);
y = getRandomInt(left.length);
combined = `${x},${y}`;
attempts += 1;
}
all_possible_combinations.push(combined);
}
// console.log(`It took ${attempts} attempts to fill ${all_possible_combinations.length} slots!`);
// Now that we have all possible swaps, calculate the results of those swaps.
let all_posible_swaps = [];
for (let combo of all_possible_combinations) {
let clonedLeft = [...left];
let split = combo.split(',');
let x = parseInt(split[0], 10);
let y = parseInt(split[1], 10);
clonedLeft[y] = left[x];
clonedLeft[x] = left[y];
all_posible_swaps.push(clonedLeft.join(''));
}
// Now check for matches
let total_matches = 0;
for (let swap of all_posible_swaps) {
if (swap == right) {
total_matches += 1;
}
}
// If it's correct, there should be exactly 2 matches.
return total_matches === 2;
}
function validateSwaps(swapArray, original) {
let output = [];
for (var arr of swapArray) {
output.push(checkSwaps(arr, original));
}
console.log(swapArray, output);
return output;
}
module.exports = function () {
validateSwaps(['BACDE', 'EBCDA', 'BCDEA', 'ACBED'], 'ABCDE');//,[true, true, false, false]
validateSwaps(['32145', '12354', '15342', '12543'], '12345');//,[true, true, true, true]
validateSwaps(['9786', '9788', '97865', '7689'], '9768');//,[true, false, false, false]
validateSwaps(['123', '321', '132', '13', '12'], '213');//, [true, false, false, false, false]
validateSwaps(['123', '1234', '1235'], '12');//, [false, false, false]
validateSwaps(['123', '123', '123'], '133');//, [false, false, false]
validateSwaps(['132', '321', '213'], '123');//, [true, true, true]
console.log('Done');
};
So... my previous answer was probably the least efficient possible way to do this. If anyone is curious, here's another way, using a state machine. Basically I iterate both the string being checked and the string I'm checking against at the same time, and run each letter through the state machine. You can see the progression in the IterationState enum.
I only included the core logic below:
#[derive(PartialEq,Debug)]
enum IterationState {
/// Either we have not iterated any characters, or all the characters have matched so far.
NoSwapsFound,
/// One set of characters have been found that don't match.
SwapFound(u8, u8),
/// A second set of characters have been found that don't match, and those equal the first set we found (except swapped)
SwapMatchFound,
/// We found too many swaps, or the swaps we found did not match
Invalid,
/// We found exactly 1 set of swaps and have finished iterating the entire string
Success
}
impl IterationState {
pub fn is_in_final_state(&self) -> bool {
match self {
IterationState::Invalid | IterationState::Success => true,
_ => false
}
}
}
// State machine!
fn iterate(current_state:IterationState, left:u8, right:u8) -> IterationState {
let new_state = match current_state {
IterationState::NoSwapsFound => match left == right {
true => IterationState::NoSwapsFound,
false => IterationState::SwapFound (left, right)
},
IterationState::SwapFound(l, r) => match left == right {
true => IterationState::SwapFound(l, r),
false => match left == r && right == l {
true => IterationState::SwapMatchFound,
false => IterationState::Invalid
}
},
IterationState::SwapMatchFound => match left == right {
true => IterationState::SwapMatchFound,
false => IterationState::Invalid
},
IterationState::Invalid => IterationState::Invalid,
IterationState::Success => IterationState::Success
};
// println!("{},{} {:?} {:?}", left, right, current_state, new_state);
new_state
}
fn check_strings(left:String, right:String) -> bool {
// It will never succeed if the lengths are not the same.
if left.len() != right.len() {
return false;
}
// Create two iterators, left & right.
let mut left_bytes = left.bytes();
let mut right_bytes = right.bytes();
// Set up the initial state
let mut state = IterationState::NoSwapsFound;
// Loop until either the state machine returns a fail code, or until we're out of letters.
while !state.is_in_final_state() {
// First get the next charaters from both strings in sequence.
// Rust returns that as an Option<T>, which has two possible values
// Some or None. None means end of list.
state = match (left_bytes.next(), right_bytes.next()) {
// This case matches that both have a value.
(Some(l), Some(r)) => iterate(state, l, r),
// This case matches that both iterators have completed.
// Since both cases have completed, if the state is that the swap match has been found,
// then we're successful! Any other status is a failure.
(None, None) => match state {
IterationState::SwapMatchFound => IterationState::Success,
_ => IterationState::Invalid
}
// This case should never happen (where one iterator still has values and the other does not)
_ => panic!()
};
}
state == IterationState::Success
}
I'm using rust because rust's enums support storing values, and the pattern matching works great for state machines.