DEV Community

Daily Challenge #5 - Ten Minute Walk

dev.to staff on July 02, 2019

Hey there, it's time to get moving. Today’s challenge is modified from user @JKphobic on CodeWars: You live in a city where all roads are laid o...

Read full post

Spacie • Jul 2 '19 • Edited

My first attempt at one of these coding challenge things!

I'm not great with maths, but I'm guessing that all walks must have an even length, otherwise you can't end up back at your starting location, you'd always be one away...

If that assumption is true, then I think this works:

Basically, for each "pair" of blocks you want to walk, either add ["n", "s"] or ["e", "w"] to an array, then flatten and shuffle! Because you're always adding both a movement and it's inverse, you'll always end up where you started!

Ruby's proc / block thing still confuses me a little so I'm not sure if this is the most elegant one-liner (excluding checking for even walk length), but ayy it works!

def genWalk length
  raise "Walk length must be even!" if length % 2 != 0
  (length / 2).times.collect(&Proc.new {[%w(n s), %w(e w)].sample}).flatten.shuffle
end

genWalk 10
# -> ["n", "w", "n", "e", "w", "s", "e", "w", "e", "s"]

Corey Alexander • Jul 2 '19

Great solution! I believe your assumption holds up and makes this solution nice and elegant!

Great job on your first challenge too!!

jmc • Jul 3 '19

nice 🤩

Jaime López • Jul 2 '19

Here my contribution with javascript language:

function getWalkSteps(walkTime) {
  if(walkTime % 2 > 0) {
    throw new Error('You cannot come back');
  }

  const distance = walkTime/2;
  const x = Math.floor(Math.random(distance) * distance);
  const y = distance - x;

  return new Array(walkTime)
    .fill('e', 0, x)
    .fill('n', x, x+y)
    .fill('w', x+y, x+y+x)
    .fill('s', x+y+x, x+y+x+y);
}

Frederik 👨‍💻➡️🌐 Creemers • Jul 2 '19 • Edited

Here's a trivial solution in Python

def get_walk(minutes):
    if minutes % 2 != 0:
        # Only even minute times are possible, as you always need to walk the same distance east as west, 
        # andnortha s sound.
        raise ValueError("Only walks with an even number of minutes are possible")

    half = minutes / 2
    return half * ['n'] + half * ['s']

If you add the requirement that you can't walk the same street twice...

def get_walk(minutes):
    if minutes % 2 != 0:
        # Only even minute times are possible, as you always need to walk the same distance east as west, 
        # andnortha s sound.
        raise ValueError("Only walks with an even number of minutes are possible")

    # We'll return a rectangle with width 1, so the two short sides combined take 2 minutes
    # We'll divide the remaining minutes by 2 to know how long the other sides should be.
    length = (minutes - 2) / 2

    return ['n'] + length * ['e'] + ['s'] + length * ['w']

Alvaro Montoro • Jul 3 '19 • Edited

Not a great solution, but a solution.

const createRandomPath = minutes => {
  let path = [];

  // if the minutes are even, calculate path
  if (minutes % 2 === 0) {  
    // populate the array from opposite ends with complementary values
    for (let x = 0; x < minutes/2; x++) {
      const letter = Math.floor(Math.random()*4);
      path[x] = "nsew".charAt(letter);
      path[minutes-x-1] = "snwe".charAt(letter);
    }

    // randomize path
    path.sort((a,b) => Math.floor(Math.random()*2) ? 1 : -1);
  }

  // return the generated array or an empty array if steps are odd
  return path;
}

And a one-liner but not really randomized, just going north-then-south:

const f=m=>m%2?[]:Array(m).fill("n",0,m/2).fill("s",m/2)

And the link to a demo on CodePen

E. Choroba • Jul 3 '19

Just make sure the number of s's and n's is the same, and the same for w's and e's.

Perl solution:

use List::Util qw{ shuffle };

sub walk {
    shuffle map { int rand 2 ? ('n', 's') : ('w', 'e') } 1 .. $_[0] / 2
}

margo1993 • Nov 11 '19

type PersonPosition struct {
    xAxis int
    yAxis int
}

func GenerateWalk(minutes int) ([]string, error) {
    personPosition := PersonPosition{0, 0}
    var walkingRoute []string

    if minutes % 2 != 0 {
        return walkingRoute, errors.New("Minutes must be even number, otherwise you can't end on starting point")
    }

    rand.Seed(time.Now().UnixNano())
    directions := []string{"n", "s", "e", "w"}

    for i := 0; i < minutes; i++ {

        personYAxis := personPosition.yAxis
        personXAxis := personPosition.xAxis
        distanceFromHome := abs(personYAxis) + abs(personXAxis)
        timeToGoHome := minutes - i
        if personYAxis >= 0 && timeToGoHome  == distanceFromHome{
            directions = removeItemFromArray(directions, "n")
        }

        if personYAxis <= 0 && timeToGoHome == distanceFromHome {
            directions = removeItemFromArray(directions, "s")
        }

        if personXAxis >= 0 && timeToGoHome == distanceFromHome {
            directions = removeItemFromArray(directions, "e")
        }

        if personXAxis <= 0 && timeToGoHome == distanceFromHome {
            directions = removeItemFromArray(directions, "w")
        }

        direction := rand.Intn(len(directions))
        route := directions[direction]
        walkingRoute = append(walkingRoute, route)

        switch route {
        case "n":
            personPosition.yAxis += 1
        case "s":
            personPosition.yAxis -= 1
        case "e":
            personPosition.xAxis += 1
        case "w":
            personPosition.xAxis -= 1
        }
    }

    return walkingRoute, nil
}

func removeItemFromArray(array []string, item string) []string {
    for i,  v:= range array {
        if v == item {
            return append(array[:i], array[i+1:]...)
        }
    }
    return array
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Corey Alexander • Jul 3 '19 • Edited

Barely in before/at midnight!

But here is my Rust version!

I took a bit of a different route! @spaciecat killed the simple algorithm answer so I wanted to do something different!

I decided to make a program that lets the user build the path they want to take! Cause why not let the User choose where to explore! I might clean this up and turn it into a full post sometime soon!

Here is a really quick demo GIF

use std::fmt;
use std::io;
use std::io::prelude::*;

fn parse_time_of_walk(user_input: &str) -> Result<u32, &'static str> {
    let parsed_input_result: Result<u32, _> = user_input.parse();
    match parsed_input_result {
        Ok(i) => {
            if i % 2 == 0 {
                Ok(i)
            } else {
                Err("Walk time must be an even number or we will not be able to get back to where we started")
            }
        }
        Err(_) => Err("Could not parse the walk time"),
    }
}

#[derive(Debug, PartialEq, Clone)]
enum Direction {
    North,
    South,
    East,
    West,
}

impl Direction {
    fn will_take_me_home(&self, current_position: (i32, i32)) -> bool {
        match self {
            Direction::North => current_position.1 < 0,
            Direction::South => current_position.1 > 0,
            Direction::East => current_position.0 < 0,
            Direction::West => current_position.0 > 0,
        }
    }

    fn to_str(&self) -> &'static str {
        match self {
            Direction::North => "North",
            Direction::South => "South",
            Direction::East => "East",
            Direction::West => "West",
        }
    }

    fn direction_diff(&self) -> (i32, i32) {
        match self {
            Direction::North => (0, 1),
            Direction::South => (0, -1),
            Direction::East => (1, 0),
            Direction::West => (-1, 0),
        }
    }
}

impl fmt::Display for Direction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Direction::North => write!(f, "North"),
            Direction::South => write!(f, "South"),
            Direction::East => write!(f, "East"),
            Direction::West => write!(f, "West"),
        }
    }
}

fn options_availible(current_position: (i32, i32), minutes_left: u32) -> Option<Vec<Direction>> {
    if current_position == (0, 0) && minutes_left == 0 {
        return Some(vec![]);
    }

    let distance_from_origin = current_position.0.abs() + current_position.1.abs();

    if distance_from_origin > minutes_left as i32 {
        None
    } else {
        let all_options: Vec<Direction> = vec![
            Direction::North,
            Direction::South,
            Direction::East,
            Direction::West,
        ];

        let can_take_detour = distance_from_origin < minutes_left as i32;

        let options = all_options
            .iter()
            .filter(|direction| direction.will_take_me_home(current_position) || can_take_detour)
            .cloned()
            .collect();
        Some(options)
    }
}

fn chosen_direction(input: &str) -> Option<Direction> {
    let lower = input.to_ascii_lowercase();
    if lower.starts_with("n") {
        Some(Direction::North)
    } else if lower.starts_with("e") {
        Some(Direction::East)
    } else if lower.starts_with("w") {
        Some(Direction::West)
    } else if lower.starts_with("s") {
        Some(Direction::South)
    } else {
        None
    }
}

fn directions_to_string(path: &Vec<Direction>) -> String {
    path.iter()
        .map(Direction::to_str)
        .collect::<Vec<_>>()
        .join(", ")
}

fn main() -> Result<(), &'static str> {
    println!("Hey I heard you want to take a walk!");
    println!("How long (in minutes) should we walk for?");
    let stdin = io::stdin();
    let mut stdin_lines = stdin.lock().lines();
    let user_input_minutes = stdin_lines.next().unwrap().unwrap();

    let mut minutes_left = parse_time_of_walk(&user_input_minutes)?;
    let mut current_position = (0, 0);
    let mut path: Vec<Direction> = vec![];

    let mut options = options_availible(current_position, minutes_left);
    while minutes_left > 0 && options.is_some() {
        let unwrapped_options = options.unwrap();

        println!("\nYou have {} minutes left", minutes_left);
        println!("Which direction would you like to go?");
        println!(
            "So far you'r path has been: {}",
            directions_to_string(&path)
        );
        println!(
            "Your current options are: {}",
            directions_to_string(&unwrapped_options)
        );

        let mut chosen_direction_option = chosen_direction(&stdin_lines.next().unwrap().unwrap());
        while chosen_direction_option.is_none() {
            chosen_direction_option = chosen_direction(&stdin_lines.next().unwrap().unwrap());
        }

        let chosen_direction = chosen_direction_option.unwrap();
        println!("You chose: {}", chosen_direction);

        current_position.0 += chosen_direction.direction_diff().0;
        current_position.1 += chosen_direction.direction_diff().1;
        path.push(chosen_direction);
        minutes_left -= 1;
        options = options_availible(current_position, minutes_left);
    }

    if minutes_left == 0 {
        println!(
            "YAY we made it! Here is the path we took: {}",
            directions_to_string(&path)
        );
    } else if options.is_none() {
        println!("OH NO! We won't be able to make it back in time! Try another path.");
        println!(
            "Here is what you tried this time: {}",
            directions_to_string(&path)
        );
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn parse_time_of_walk_test() {
        assert_eq!(
            parse_time_of_walk("3"),
            Err("Walk time must be an even number or we will not be able to get back to where we started")
        );
        assert_eq!(
            parse_time_of_walk("five"),
            Err("Could not parse the walk time")
        );
        assert_eq!(parse_time_of_walk("4"), Ok(4));
    }

    #[test]
    fn test_all_options_availible() {
        let output = options_availible((0, 0), 10);
        let all_options = vec![
            Direction::North,
            Direction::South,
            Direction::East,
            Direction::West,
        ];
        assert_eq!(output, Some(all_options));
    }

    #[test]
    fn test_impossible_options() {
        assert_eq!(options_availible((0, -10), 1), None);
        assert_eq!(options_availible((1, 10), 10), None);
        assert_eq!(options_availible((-1, 10), 10), None);
    }

    #[test]
    fn test_already_at_origin_and_no_minutes_left() {
        assert_eq!(options_availible((0, 0), 0), Some(vec![]));
    }

    #[test]
    fn test_north_only_option() {
        let output = options_availible((0, -1), 1);
        assert_eq!(output, Some(vec![Direction::North]));
    }
}

jmc • Jul 3 '19 • Edited

Spacie's algo, in Clojure:

(def pairs
  [["n" "s"] ["e" "w"]])

(defn walk [n]
  (-> (quot n 2)
      (repeatedly #(rand-nth [["n" "s"] ["e" "w"]]))
      flatten
      shuffle))

Ilyes Chouia • Aug 25 '19

PHP


function take_a_walk(int $distance){

    if($distance %2 == 1){ 
        throw new Exception("take an even number of steps or no return home! <br>");
    }
    $steps = [];
    $directions = ['n', 'e', 's', 'w'];
    for($i = 1; $i <= $distance; $i+=2){
        $index = array_rand($directions);
        $steps[] = $directions[$index];
        $steps[] = $directions[($index + 2) %4];
    }
    shuffle($steps);
    $steps = implode(', ', $steps) . PHP_EOL;
    return $steps;
}
echo "Steps to take : " . take_a_walk(58);

kesprit • Oct 23 '19

My solution in Swift language :

func generateMinutesWalk(minutes: Int) -> [String]? {
    guard minutes % 2 == 0 else {
        print("Minutes is odd")
        return nil
    }

    let coordinates = ["N", "O", "S", "E"]
    var travel = [String]()

    for _ in 0..<minutes / 2 {
        travel.append(coordinates[Int.random(in: 0..<coordinates.count)])
    }
    travel.forEach { value in
        if let index = coordinates.firstIndex(of: value) {
            travel.append(coordinates[(index + 2) % coordinates.count])
        }
    }

    return travel
}

Dimitri Lahaye • Jul 9 '20

During my reflexion about this challenge, I figured out that if input is an odd number, you will never be able to go back at your start position.

Here my JS implementation:

function direction(time) {
  if (time % 2 > 0) {
    throw 'You will never go back!!';
  }
  const ahead = Math.ceil(time/4),
    turn = Math.floor(time/4);
    return ('n'.repeat(ahead) + 'w'.repeat(turn) + 's'.repeat(ahead) + 'e'.repeat(turn)).split('');
}

// let's test it

try {
  console.log(direction(4)); // print ["n", "w", "s", "e"]
} catch (e) {
  console.log(e);
}

try {
  console.log(direction(1));
} catch (e) {
  console.log(e); // You will never go back!!
}

try {
  console.log(direction(3));
} catch (e) {
  console.log(e); // You will never go back!!
}

Martin Himmel • Jul 3 '19

PHP

function go_for_a_walk(int $distance) {
    if ($distance % 2 == 1) {
        throw new Exception("There's no place like home. Unfortunately, you won't return home with an odd number of steps.");
    }

    $steps = [];
    $directions = ['n', 'e', 's', 'w'];
    while ($distance > 0) {
        $index = array_rand($directions);
        $steps[] = $directions[$index];
        $steps[] = $directions[($index + 2) % 4];
        $distance -= 2;
    }
    shuffle($steps);
    return $steps;
}

echo implode(', ', go_for_a_walk(10)) . PHP_EOL;

Ryan Smith • Jul 3 '19 • Edited

Here is my JavaScript solution.

My approach was to depart in some random direction, duplicate that initial set of directions, reverse each individual direction within that copy (north goes to south, etc.), then reverse that entire copy to return to the starting point.

/**
 * Generate directions for a walk on a grid that returns to its origin point where one block takes one minute.
 */
function generateWalk (timeInMinutes) {
  const midpoint = Math.trunc(timeInMinutes / 2)
  const compass = ['n', 'e', 's', 'w']
  let departureDirections = []
  let returnDirections = []

  for (let i = 0; i < midpoint; i++) {
    // For the first half of the walk, generate random directions.
    departureDirections[i] = compass[Math.floor(Math.random() * Math.floor(compass.length))]

    // If the direction's index is less than 2 (north, east), shift forward two directions to its reverse direction. Otherwise if it is greater than 2 (south, west), shift it backward two directions to its reverse direction.
    if (compass.indexOf(departureDirections[i]) < 2) {
      returnDirections[i] = compass[compass.indexOf(departureDirections[i]) + 2]
    } else {
      returnDirections[i] = compass[compass.indexOf(departureDirections[i]) - 2]
    }
  }

  // Reverse the return directions in order to return to the starting point.
  returnDirections.reverse()

  // Concatenate the departure array with the return array to get the full directions.
  return departureDirections.concat(returnDirections)
}

The part I had trouble with was swapping each individual direction. I stored my directions in an array that follows a compass because I figured that the reverse direction is always two away: north's array position + 2 = south, east + 2 = west. I ran into some trouble shifting the directions because I could not add two in all cases because it would go outside of the array bounds, so I put in the if-statement. I'm not sure if there is a way to "wrap" an array in JavaScript without going out of the array bounds. I believe in Python this can be done with the slice notation (double colon syntax). If anyone has a tip for JavaScript, feel free to share.

jmc • Jul 3 '19

For wrapping some sum x + y inside of a range n, you can use (x + y) % n (and of course bounds-checking with if works too).

N.B. different languages treat negative mod differently. For JS, in the negative case you'd want something like ((x % n) + n) % n instead of plain %.

Ceban Dumitru • Jul 4 '19 • Edited

BASH

#!/bin/bash
declare gps=(n s e w);
if [[ $((${1} % 2 )) = 0 ]]; then
    for (( i = ${1}; i >= 0; i-=2 )); do
        echo ${gps[$(($RANDOM%3))]};
    done;
else 
    echo "Sorry, you cannot generate way";
fi

David Figueroa • Jan 12 '20

Powershell

I went the voluntary choice route with a voluntary initial route, and reversing it to get back.

function New-WalkPattern {
    [cmdletbinding()]
    param(
        [parameter(ValueFromPipelineByPropertyName)]
        [ValidateRange(4,30)]
        [int]$WalkTime = 14
    )

    if ($WalkTime % 2 -gt 0) {
        $WalkTime --
    }
    $WalkTimeArray = [char[]]::new($WalkTime)

    $LastDirection = 'x' #picking an invalid direction on purpose
    $UserSteps = $WalkTime / 2
    $ReverseStepTracker = -1

    $North   = [System.Management.Automation.Host.ChoiceDescription]::New('&North', 'Walk North')
    $East    = [System.Management.Automation.Host.ChoiceDescription]::New('&East', 'Walk East')
    $South   = [System.Management.Automation.Host.ChoiceDescription]::New('&South', 'Walk South')
    $West    = [System.Management.Automation.Host.ChoiceDescription]::New('&West', 'Walk West')
    $Options = [System.Management.Automation.Host.ChoiceDescription[]]($North, $East, $South, $West)
    $Title   = 'Which Direction'
    $Message = 'Pick a direction to walk'

    function Test-IfWalkDirectionIsRepeated {
        param(
            [string]$ThisDirection
        )
        if ($LastDirection -eq $ThisDirection) {
            Write-Warning -Message 'You cannot travel the same direction twice in a row!'
            $Result = $true
        }
        else {
            $LastDirection = $ThisDirection
            $Result = $false
        }
        return $Result
    }

    for ($i = 0; $i -lt $UserSteps; $i++) {
        $Result  = $host.ui.PromptForChoice($Title, $Message, $Options, 0)
        switch ($Result) {
            '0' {
                    if (Test-IfWalkDirectionIsRepeated -ThisDirection 'N')
                    {
                        $i ++
                        $ReverseStepTracker ++
                    }
                    else {
                        $WalkTimeArray[$i]  = 'N'
                        $WalkTimeArray[$ReverseStepTracker] = 'S'
                        $ReverseStepTracker --
                    }
                    break
            }
            '1' {
                    if (Test-IfWalkDirectionIsRepeated -ThisDirection 'E')
                    {
                        $i ++
                        $ReverseStepTracker ++
                    }
                    else {
                        $WalkTimeArray[$i]  = 'E'
                        $WalkTimeArray[$ReverseStepTracker] = 'W'
                        $ReverseStepTracker --
                    }
                    break
            }
            '2' {
                    if (Test-IfWalkDirectionIsRepeated -ThisDirection 'S')
                    {
                        $i ++
                        $ReverseStepTracker ++
                    }
                    else {
                        $WalkTimeArray[$i]  = 'S'
                        $WalkTimeArray[$ReverseStepTracker] = 'N'
                        $ReverseStepTracker --
                    }
                    break
            }
            '3' {
                    if (Test-IfWalkDirectionIsRepeated -ThisDirection 'W')
                    {
                        $i ++
                        $ReverseStepTracker ++
                    }
                    else {
                        $WalkTimeArray[$i]  = 'W'
                        $WalkTimeArray[$ReverseStepTracker] = 'E'
                        $ReverseStepTracker --
                    }
                    break
            }
        }

    }
    Write-Output $('Your walk path is: {0}' -f ($WalkTimeArray -join ','))
}

Jarod Smith • Aug 19 '19

// in general we will create a sequence which just retraces itself after a certain time.
function generateWalkSequence(time) {
  if(time % 2 != 0) 
    throw new Error('Time must be even');
  let walkSequence = [];
  let oppositeDirections = [];
  let nextDirection = 'n';
  const directions = [...'nswe'];
  for(let i = 0; i < time/2; i++) {
    // loop selection after index 3
    walkSequence[i] = (nextDirection = directions[i % 4]);
    oppositeDirections[i] = (getComplement(nextDirection));
  }
  return [...walkSequence,...oppositeDirections.reverse()];
}

function getComplement(direction) {
  switch (direction) {
    case 'n':
      return 's';
    case 's':
      return 'n';
    case 'e':
      return 'w';
    case 'w':
      return 'e';
  }
}

Ganesh Prasad • Aug 24 '19

const generate = mins => isNaN(mins) || Number(mins) % 2 !== 0 ? null
    : Array(Number(mins)/2).fill('ns').join('');