Optimal solution to go to opposite corner of a rectangle

Question

Your job is to write a program that finds the optimal number of moves it takes to get from the lower-left corner of a rectangle to the upper-right corner directly opposite.

Your program will accept input as an ordered pair (width, height). These will be the dimensions of the rectangle you will work with. Your program will create an ASCII-art of the solution (use . for empty square and # for part of the solution, X for starting square) and count the number of moves it takes to reach the endpoint. Diagonal moves are not allowed. If there are multiple solutions, choose one to output.

The shortest program in bytes wins.

Example

Input: (4, 5)

Output:

..##
..#.
.##.
.#..
X#..

Move count: 7

Answer 1

Retina, 54 53 bytes

\d+
$*.
S_`(?<=(.+)¶.*).|\D
T`.`#`.¶|.*$
:m-1=`^#
X
#

Takes input separated by a linefeed and outputs the solution grid followed by the move count.

Try it online!

Explanation

\d+
$*.

Turn both integers into that many .s, i.e. convert them to unary.

S_`(?<=(.+)¶.*).|\D

This builds a grid of .s, by matching each . in the unary height and capturing the unary representation of the width. The S activates split mode which returns the captured strings, and the |\D and _ together ensure that everything else is removed from the string.

T`.`#`.¶|.*$

This turns the last character of each line as well as the entire last line into #s.

:m-1=`^#
X

This uses a ton of options to convert only the first # on the last row to X (we need to make sure that only the last row is affected because of width-1 inputs). m activates multi-line mode which makes ^ match the beginning of lines. -1= tells Retina to perform the substitution only on the last match. Finally, : switches off the default silent mode such that the grid is printed to STDOUT as an intermediate result.

#

Finally, we simply count the number # in the string, which corresponds to the number of moves.

Answer 2

Pyke, 26 bytes

DtQ+RtF; Q\.*t\#+)\X\#Qt*+

Try it here

---

Or a noncompetitive 34 bytes, add apply node with an ast)

jUa]Dm!X|RZjht]q+".#X"R@)Fs
);jmts

Try it here!

Or 30 bytes if allowed spaces as padding

jUa]Dm!X|RZjht]q+".#X"R@)Pjmts

Answer 3

Pyth, 32 29 24 bytes

AtMQVH+*\.G\#;+\X*\#G+GH

Try it online!

Sample input:

(4, 5)

Sample output:

...#
...#
...#
...#
X###
7

How it works:

AtMQVH+*\.G\#;+\X*\#G+GH
                           assign('Q',eval_input())
AtMQ                       assign('[G,H]',Pmap(lambda d:tail(d),Q))
    VH       ;             for N in range(H):
      +*\.G\#                  implicit_print(plus(times(".",G),"#"))
              +\X*\#G      implicit_print(plus("X",times("#",G)))
                     +GH   implicit_print(plus(G,H))

---

Previous attempt:

JthQK@Q1+*++*\.J\#btK+\X*\#Jt+JK

Try it online!

Sample input:

(4, 5)

Sample output:

...#
...#
...#
...#
X###
7

How it works:

JthQK@Q1+*++*\.J\#btK+\X*\#Jt+JK
                                 assign('Q',eval_input())        --Q is now an official pair of numbers (4, 5)
JthQ                             assign("J",decrement(first(Q))) --gets the first element, and then take 1 from it, and assign it to J
    K@Q1                         assign("K",lookup(Q,1))         --K is now the second element (count from 0) of the pair.
        +            +\X*\#J     concat(-----------------------------------------------------------,concat("X",times("#",J)))
         *         tK                   repeat(--------------------------------------,decrement(K))
          +       b                            concat(-------------------------,"\n")
           +    \#                                    concat(-------------,"#")
            *\.J                                             repeat(".",J)
                            t+JK decrement(add(J,K)) <--- auto-print

Answer 4

CJam, 35 33 bytes

q~\(_2$(+p'.*a*'#f+)W%_"X#"era+N*

Takes input in the form width height and outputs the move count on the first line, followed by the solution grid.

Test it here.

This also works for the same byte count:

q~\('.*a*'#f+)W%_"X#"era+N*_'#e=p

Answer 5

Ruby, 48 bytes

This is an anonymous function, which according to this meta post is acceptable unless the question states "full program." I wouldn't normally be pedantic about this but the problem is very simple and doing a program would be a significant % increase to the score.

Input is two arguments. Return value is an array containing the ASCII art string and the number of # in the path.

->w,h{[(?.*(w-=1)+'#
')*(h-=1)+?X+?#*w,w+h]}

In test program

f=->w,h{[(?.*(w-=1)+'#
')*(h-=1)+?X+?#*w,w+h]}

puts f[4,5]

Output

...#
...#
...#
...#
X###
7

It's just a string of h-1 rows of w-1 dots, followed by a # and newline. I put the # at the end in order to use a single #\n literal for both # and newline (the code contains an actual newline rather than an escape sequence.) The final row is then an X followed by w-1 #'s.

It was shorter to decrement the values of w and h during the ASCII art generation, so that the final calculation is simply w+h.

Answer 6

JavaScript (ES6), 60 bytes

w=>h=>--w+--h+`
${"."[r="repeat"](w)}#`[r](h)+`
X`+"#"[r](w)

Usage

f(4)(5)

7
...#
...#
...#
...#
X###

Answer 7

MATL, 28 26 25 bytes

+qq35IMwX"46 5Lt4$(88HG(c

EDIT (June 10, 2016): the link below includes a modification ( 5L is replaced by IL) to adapt to changes in the language

Try it online!

Explanation

+       % take two inputs. Add them
qq      % subtract 2
35      % push ASCII for '#'
IMw     % push the two inputs again. Swap them
X"      % 2D char array of '#'  repeated as indicated by inputs
46      % push ASCII for '.'
5Lt4$(  % fill all but last and row columns with that
88HG(   % fill 88 (ASCII for 'X') at linear index given by second input
c       % convert to char

Answer 8

05AB1E, 27 24 bytes

Code:

+Í,¹<'.×'#¶J²<×'X'#¹<×J,

Explanation:

+                         # Add the length and the height.
 Í                        # Decrease by two.
  ,                       # Print this value with a newline.
   ¹<'.×                  # Take the first input, decrease by 1 and multiply with ".".
        '#¶               # Push a "#"-character and a newline character.
           J              # Join the string.
            ²<            # Take the second input and decrease by 1.
              ×           # Multiply the joined string with this value.
               'X         # Push the "X"-character.
                 '#¹<×J   # Multiply the "#"-character with (first input - 1).
                       ,  # Pop and print with a newline.

Try it online!. Uses CP-1252 encoding.

Answer 9

Scala, 118 bytes

(w:Int,h:Int)=>{print(Array.fill(h-1,w-1)('.')map(new String(_))mkString("","#\n","#\nX"));Seq.fill(w-1)(print("#"))}


(w:Int,h:Int)=>{...}           //define a function with 2 Ints as parameters
print(                        //print ...   
  Array.fill(h-1,w-1)('.')    //an array of arrays with dimensions (h-1,w-1)
                              //and fill it with a dot
  map(new String(_))          //map each inner array of chars to a string
  mkString("","#\n","#\nX")   //create a string from the array, with
                              //an empty string before the array,
                              //"#\n" as a seperator between the elements
                              //and "#\nX" at the end   
);
Seq.fill(w-1)(print("#"))     //w-1 times print "#"

Answer 10

Haskell, 64 bytes

c!n=c<$[2..n]
w#h=unlines$('.'!w++"#")!h++['X':'#'!w,show$w+h-2]

Usage example:

*Main> putStr $ 4 # 5
...#
...#
...#
...#
X###
7

How it works:

c!n = c <$ [2..n]                       -- helper function: make (n-1) copies of c

                                        -- main function
                     !h                 -- (h-1) times
       ('.'!w ++ "#")                   --    (w-1) dots and a hash sign
                       ++[      ,     ] -- followed by
                          'X' : '#'!w   --    an 'X' and (w-1) hash signs
                            show$w+h-2  --    and the number of steps
unlines                                 -- join everything with newlines in-between

Answer 11

Java, 137 132 bytes

w->h->{String s="";int i=0,j;for(;i<h;i++){for(j=1;j<w;j++)s+=".";s+="#\n";}s+="X";for(j=1;j<w;j++)s+=".";s+="\n"+(w+h-2);return s;}

Answer 12

Lua, 81 bytes

Try it online!

Golfed:

w,h=(...)print((("."):rep(w-1).."#\n"):rep(h-1).."X"..("#"):rep(w-1))print(w+h-2)

Ungolfed:

w,h=4,5
print((("."):rep(w-1).."#\n"):rep(h-1).."X"..("#"):rep(w-1))
print(w+h-2)

Answer 13

Python, 48.

lambda w,h:('.'*(w-1)+'#\n')*(h-1)+'X'+'#'*(w-1)

To use it, add f= before the line above and call it like this:

f(4, 5)

Result:

...#
...#
...#
...#
X###