#!/usr/bin/perl -w

use strict;
use v5.30;

use Digest::MD5 qw(md5_hex);
my $in = 'pvhmgsws';

my @paths = [ 0, 0, '' ];

while (@paths) {
	my $p = shift @paths;
	my ($x, $y, $path) = @$p;

	if ($x == 3 && $y == 3)  {
		say $path;
		last;
	}

	my $h = md5_hex($in.$path);
	if ($y > 0 && substr($h, 0, 1) =~ /[b-f]/) {
		push @paths, [ $x, $y-1, $path.'U' ];
	}
	if ($y < 3 && substr($h, 1, 1) =~ /[b-f]/) {
		push @paths, [ $x, $y+1, $path.'D' ];
	}
	if ($x > 0 && substr($h, 2, 1) =~ /[b-f]/) {
		push @paths, [ $x-1, $y, $path.'L' ];
	}
	if ($x < 3 && substr($h, 3, 1) =~ /[b-f]/) {
		push @paths, [ $x+1, $y, $path.'R' ];
	}
}


