Skip to content
This repository has been archived by the owner on May 27, 2024. It is now read-only.

Latest commit

 

History

History
87 lines (67 loc) · 2.96 KB

SG1.md

File metadata and controls

87 lines (67 loc) · 2.96 KB

Back to README

Day #49: Who won the election?

I don't even know what they look like.
Furling. Sounds cute and fuzzy to me.

- Jonas Quinn and Jack O'Neill, "Paradise Lost".

Previously on Stargate SG-1

Arriving on P4F-976, SG-1 finally come into contact with the Furlings, one of the four great races within the Milky Way. After several days of deliberation with the Furling Directorate, the Tauri finally have access to the knowledge they have been searching for.

The Furlings, having provided assistance with the Ancient's expansion into the Milky Way, have extensive knowledge of the Stargate Network and it's components. One such component, the Dial Home Device, has caused many disasters at Stargate Command through it's absence. Thankfully, the Furlings have all the necessary blueprints for it's construction, and have handed copies over to the Tauri. After beginning mass production of the control crystals necessary for it's function, Stargate Command has hit a snag. The Ancients had designed the control crystals to function if their inner pathways are as efficient as possible - essentially, the pathways must choose the shortest path between two nodes. Stargate Command has turned to you - a software engineer - to fix their problems.

Your Mission

Given a string containing the current state of the control crystals inner pathways (labeled as 'X') and its gaps (labeled as '.'), generate the shortest path from the start node (labeled as 'S') to the goal node (labeled as 'G') and return the new pathway (labeled with 'P's). If no solution is possible, return the string "Oh for crying out loud..." in frustration.

The Rules

  • Nodes labeled as 'X' are not traversable.
  • Nodes labeled as '.' are traversable.
  • A pathway can be grown in 8 directions (up, down, left, right, up-left, up-right, down-left, down-right).
  • A pathway can be grown between a diagonal gap.
  • For example, given the case:

 SX.
 X..
 ..G
  • A valid solution is possible:

 SX.
 XP.
 ..G
  • As a path can be grown in the gap between the pathways
  • However, in the following case:

 SX.
 .X.
 .XG
  • A valid solution is not possible.
  • Nodes labeled 'S' and 'G' are not to be replaced with 'P' in the case of a solution.
  • The shortest solution is the one containing the least nodes labeled 'P'.

Example #1: Valid solution


SG1.wireDHD() =>

".S... \n
 XXX.. \n
 .X.XX \n
 ..X.. \n
 G...X"

return =>

".SP.. \n
 XXXP. \n
 .XPXX \n
 .PX.. \n
 G...X"

Example #2: No solution


SG1.wireDHD() =>

"S.... \n
 XX... \n
 ...XX \n
 .XXX. \n
 XX..G"

return =>

"Oh for crying out loud..."