2019 Luke 16.md

Seilkryss

Av: Didrik Pemmer Aalen

Birte befinner seg på en seilbåt helt innerst i den lange julefjorden. Hun har et ønske om å komme seg ut, slik at hun kommer seg hjem til jul, men vindforholdene gjør det vanskelig. For å komme seg ut av fjorden må hun følge disse reglene:

1. Hun kan kun krysse nordøst (x+1, y+1) og sørøst (x+1, y-1).
2. Hun må snu når hun er 20 meter fra land (i retning nord/sør).

Oppgave

Gitt følgende fjord, hvor mange ganger ender Birte opp med å krysse for å komme seg ut av fjorden når hun begynner å krysse mot nordøst?

OBS! Antall kryssinger er definert som antall strekninger hun seiler, ikke antall ganger hun snur.

Eksempel

Her er følgende definert:

B = Birte
# = Land
Tomme ruter er vann
/ og \ viser ruten til Birte i svaret

Hver rute er 10 meter lang.

Gitt følgende fjord:

####################
#    ###
#            
#
#
#
#
#
#B
###    ####     #   
####################

Blir kryssingene slik:

####################
#    ###
#            
#           /\      
#    /\    /  \    /
#   /  \  /    \  /
#  /    \/      \/
# /              
#B
###    ####     #   
####################

Og Birte ender med 5 kryssinger.

Denne gikk i det minste bedre enn gårsdagens, hehe.
Naiv løsning i Rust:

use std::fs;

struct Birte {
    x: usize,
    y: usize,
    dir: &'static Direction,
}

#[derive(PartialEq)]
enum Direction {
    Northeast,
    Southwest,
}

impl Birte {
    fn sail(&self, direction: &'static Direction) -> Birte {
        if self.dir != direction {
            return Birte {
                x: self.x + 1,
                dir: direction,
                ..*self
            };
        }
        match direction {
            Direction::Northeast => Birte {
                x: self.x + 1,
                y: self.y + 1,
                ..*self
            },
            Direction::Southwest => Birte {
                x: self.x + 1,
                y: self.y - 1,
                ..*self
            },
        }
    }
}

fn crossings(fjord: &str) -> u32 {
    let mut crossings = 1;
    let start = fjord.replace("\n", "").find("B").unwrap();
    let lines: Vec<&str> = fjord.lines().collect();
    let line_length = lines[0].chars().count();
    let mut birte = Birte {
        x: start % line_length,
        y: start / line_length,
        dir: &Direction::Southwest,
    };
    while birte.x != line_length - 1 {
        match birte.dir {
            Direction::Northeast => {
                if lines[birte.y + 1].chars().nth(birte.x + 1).unwrap() == '#'
                    || lines[birte.y + 2].chars().nth(birte.x + 1).unwrap() == '#'
                    || lines[birte.y + 3].chars().nth(birte.x + 1).unwrap() == '#'
                {
                    // We need to cross to other direction
                    birte = birte.sail(&Direction::Southwest);
                    crossings += 1;
                    continue;
                }
            }
            Direction::Southwest => {
                if lines[birte.y - 1].chars().nth(birte.x + 1).unwrap() == '#'
                    || lines[birte.y - 2].chars().nth(birte.x + 1).unwrap() == '#'
                    || lines[birte.y - 3].chars().nth(birte.x + 1).unwrap() == '#'
                {
                    // We need to cross to other direction
                    birte = birte.sail(&Direction::Northeast);
                    crossings += 1;
                    continue;
                }
            }
        }
        birte = birte.sail(&birte.dir);
    }
    crossings
}

fn main() {
    let fjord = fs::read_to_string("fjord.txt").unwrap();
    println!("{}", crossings(&fjord));
}

#[test]
fn test_crossings() {
    let fjord = "####################\n\
                 #    ###            \n\
                 #                   \n\
                 #                   \n\
                 #                   \n\
                 #                   \n\
                 #                   \n\
                 #                   \n\
                 #B                  \n\
                 ###    ####     #   \n\
                 ####################";
    assert_eq!(crossings(&fjord), 5);
}

Kjøretiden på ca 50ms

Dagens Haskell.

import           Data.List

data Dir
  = Up
  | Down

main :: IO ()
main = readFile "input/fjord.txt" >>= print . solve 45 Up 1 . parse

parse :: String -> [(Int, Int)]
parse = drop 2 . map count . transpose . lines
  where
    count xs =
      let (octothorpes, rest) = span (== '#') xs
       in ( length octothorpes
          , length octothorpes + length (takeWhile (== ' ') rest))

solve :: Int -> Dir -> Int -> [(Int, Int)] -> Int
solve _ _ rounds [] = rounds
solve y Up trips ((top, _):xs)
  | y <= top + 3 = solve y Down (trips + 1) xs
  | otherwise = solve (y - 1) Up trips xs
solve y Down trips ((_, bottom):xs)
  | y > bottom - 3 = solve y Up (trips + 1) xs
  | otherwise = solve (y + 1) Down trips xs

Ble mye knoting med denne for å få rett svar og ser ikke ut.

package main

import (
	"bufio"
	"fmt"
	"os"
)

type Point struct {
	X, Y int
}

var (
	countCrossing int = 1
	fjord         [][]rune
	location      Point
	direction     Point = Point{X: 1, Y: -1}
	xlength       int   = 0
)

func elementExists(coordinate Point) bool {
	if coordinate.Y >= 0 && coordinate.Y < len(fjord) {
		if coordinate.X >= 0 && coordinate.X < len(fjord[coordinate.Y]) {
			return true
		} else {
			return false
		}
	} else {
		return false
	}
}

func (current Point) CalcNextStep() Point {
	return Point{
		X: current.X + direction.X,
		Y: current.Y + direction.Y,
	}
}

func GetNextStep() {
	var threeStepAhead = location.CalcNextStep().CalcNextStep().CalcNextStep()
	if elementExists(threeStepAhead) {
		if string(fjord[threeStepAhead.Y][threeStepAhead.X]) == "#" {
			direction = Point{X: direction.X, Y: direction.Y * -1}
			countCrossing += 1
			location = Point{X: location.X + 1, Y: location.Y}
		} else {
			location = location.CalcNextStep()
		}
	} else {
		location = location.CalcNextStep()
	}
}

func sail() {
	for {
		GetNextStep()

		if location.X == xlength {
			break
		}
	}
}

func main() {
	file, fileError := os.Open("./fjord.txt")
	if fileError != nil {
		fmt.Println("Error opening file")
	}
	defer file.Close()

	scanner := bufio.NewScanner(file)
	scanner.Split(bufio.ScanLines)

	for scanner.Scan() {
		fjord = append(fjord, []rune(scanner.Text()))
	}

	xlength = len(fjord[0])

	for index, _ := range fjord {
		for index2, value2 := range fjord[index] {
			if string(value2) == "B" {
				location.X = index2
				location.Y = index
			}
		}
	}

	sail()
	fmt.Println(countCrossing)
}

Ble mye knot i dag, gjorde samme feil som mange andre (regnet antall svinger), og ble off-by-one:

ReasonML / BuckleScript

let getBirte = fjord => {
  let index = ref((0, 0));

  for (i in 0 to Array.length(fjord) - 1) {
    for (j in 0 to Array.length(fjord[i]) - 1) {
      if (fjord[i][j] == "B") {
        index := (i, j);
      };
    };
  };

  index^;
};

type direction =
  | NorthEast
  | SouthEast;

exception UnknownSymbol(string);

let calculateTurns = fjord => {
  let rec calc = (fjord', (i, j), turns, direction) =>
    if (Array.length(fjord'[i]) == j) {
      turns;
    } else {
      let borderIndex =
        switch (direction) {
        | NorthEast => i - 2
        | SouthEast => i + 2
        };

      switch (fjord'[borderIndex][j], direction) {
      | ("#", NorthEast) => calc(fjord', (i + 1, j), turns + 1, SouthEast)
      | ("#", SouthEast) => calc(fjord', (i - 1, j), turns + 1, NorthEast)
      | (" ", NorthEast) => calc(fjord', (i - 1, j + 1), turns, direction)
      | (" ", SouthEast) => calc(fjord', (i + 1, j + 1), turns, direction)
      | (any, _) => raise(UnknownSymbol(any))
      };
    };

  calc(fjord, getBirte(fjord), 1, NorthEast);
};

Node.Fs.readFileAsUtf8Sync("fjord.txt")
|> Js.String.trim
|> Js.String.split("\n")
|> Array.map(el => el |> Js.String.split(""))
|> calculateTurns
|> Js.log;

class Luke16 : KnowItJuleKalenderLuke
{
    public Task<int> OpenAsync()
    {
        var parser = new FjordParser();
        var fjord = parser.Parse();
        var birte = fjord.Birte;
        birte.SeilHjem(fjord);
        return Task.FromResult(birte.Vendinger + 1);
    }
}

class FjordSlice
{
    public int NordligBredde { get; set; }
    public int SørligBredde { get; set; }
    public bool Vann { get; set; } = false;
}

class Fjord
{
    public int Bredde { get; set; } = 0;
    public int Lengde => (Slices == null) ? 0 : Slices.Length;
    public FjordSlice[] Slices { get; set; }
    public Birte Birte { get; set; }
}

enum Retning { Sydover, Nordover };

class Birte
{
    public int Y { get; set; }
    public int Vendinger { get; set; }
    public Retning Retning { get; set; } = Retning.Nordover;

    public void SeilHjem(Fjord fjord)
    {
        for (int i = 1; i < fjord.Slices.Length; i++)
        {
            Move(fjord, fjord.Slices[i]);
        }
    }

    public void Move(Fjord fjord, FjordSlice slice)
    {
        switch (Retning)
        {
            case Retning.Sydover:
                {
                    int y = Y - 1;
                    int rom = y - slice.SørligBredde;
                    if (rom >= 2)
                    {
                        Y = y;
                    }
                    else
                    {
                        y = Y + 1;
                        Vendinger++;
                        Retning = Retning.Nordover;
                    }
                }
            break;
            case Retning.Nordover:
                {
                    int y = Y + 1;
                    int rom = fjord.Bredde - slice.NordligBredde - y - 1;
                    if (rom >= 2)
                    {
                        Y = y;
                    }
                    else
                    {
                        y = Y - 1;
                        Vendinger++;
                        Retning = Retning.Sydover;
                    }
                }
             break;
        }
    }

}

class FjordParser
{
    public Fjord Parse()
    {   
        var r = new StreamReader(@"D:\dev\rep\challenges\knowitkodekalender19\data\FjordenBaby.txt");

        Fjord fjord = new Fjord();
        
        var line = r.ReadLine();
        int n = line.Length;
        fjord.Slices = new FjordSlice[n];
        for (var i = 0; i < n; i++) fjord.Slices[i] = new FjordSlice();
        while (line != null)
        {
            fjord.Bredde++;
            for (int i = 0; i < n; i++)
            {
                var slice = fjord.Slices[i];
                var c = line[i];
                switch (c)
                {
                    case ' ': 
                        slice.Vann = true; 
                    break;
                    case 'B':
                        fjord.Birte = new Birte { Y = fjord.Bredde };
                    break;
                    case '#':
                        if (slice.Vann) 
                            slice.SørligBredde++;
                        else
                            slice.NordligBredde++;
                    break;
                    default: throw new Exception("unexpected: " + c);
                }
            }
            line = r.ReadLine();
        }

        fjord.Birte.Y = fjord.Bredde - fjord.Birte.Y;
        return fjord;
    }
}

Ikke noe tid til å rydde opp i tankevirksomhet og hacks i dag:

def fjordify(f):
    lines = [line.strip() for line in open(f).readlines()]
    width = len(lines[0])
    fjord = {
        'map': [],
        'boat': None,
    }

    for y, line in enumerate(lines):
        row = [' '] * width

        for x in range(0, len(line)):
            if line[x] == '#':
                row[x] = '#'
            elif line[x] == 'B':
                row[x] = 'B'
                fjord['boat'] = (x, y)

        fjord['map'].append(row)

    return fjord


def navigate(fjord):
    x, y = fjord['boat']
    d = 'ne'
    changed = 0

    while True:
        x += 1

        if x == len(fjord['map'][0]):
            break

        if d == 'ne':
            y -= 1
        elif d == 'se':
            y += 1

        fjord['map'][y][x] = '/' if d == 'ne' else '\\'

        if (d == 'ne' and fjord['map'][y-3][x] == '#') or \
           (d == 'se' and fjord['map'][y+3][x] == '#'):
            changed += 1

            if d == 'ne':
                y -= 1
                d = 'se'
            else:
                d = 'ne'
                y += 1

    return changed + 1


def print_map(fjord):
    print("\n")
    for row in fjord['map']:
        print(''.join(row))


def test_fjordify():
    fjord = fjordify('input/fjord.test.txt')

    assert len(fjord['map']) == 11
    assert len(fjord['map'][0]) == 20
    assert fjord['boat'] == (1, 8)

    result = navigate(fjord)
    assert 5 == result


if __name__ == '__main__':
    fjord = fjordify('input/fjord.txt')
    print(navigate(fjord))

F# - burde ha testet off by 1 med en gang, gikk meg helt bort med sjekker både foran/bak/++

open System.IO

let filStiProd = Path.Combine([| __SOURCE_DIRECTORY__; "fjord.txt" |])
let filStiTest = Path.Combine([| __SOURCE_DIRECTORY__; "test.txt" |])

let lesFil filSti = File.ReadAllLines(filSti) //    |> Array.rev

type Tilstand =
    { X: int
      Y: int
      Lengder: int
      YVelocity: int }

let tellAntallKryss filSti =
    let fjord = lesFil filSti //  |> Array.rev

    let (startX, startY) =
        let c = "B"
        fjord
        |> Array.tryFindIndex (fun (linje: string) -> linje.IndexOf(c) > 0)
        |> Option.map (fun y -> (fjord.[y].IndexOf(c), y))
        |> Option.defaultValue (0, 0)

    let fjordSlutt = fjord.[0].Length

    let startTilstand =
        { X = startX
          Y = startY
          Lengder = 1
          YVelocity = -1 }

    let skalKrysse xPos yPos yVel = fjord.[yPos + (yVel * 3)].[xPos] = '#'

    startTilstand
    |> Seq.unfold (fun b ->
        if b.X >= fjordSlutt - 1 then
            None
        else if not (skalKrysse b.X b.Y b.YVelocity) then
            let ny =
                { b with
                      X = b.X + 1
                      Y = b.Y + b.YVelocity }
            Some((0, ny.Lengder, ny.X, ny.Y), ny)
        else
            let ny =
                { b with
                      X = b.X + 1
                      Lengder = b.Lengder + 1
                      YVelocity = b.YVelocity * -1 }
            Some((1, ny.Lengder, ny.X, ny.Y), ny))

// tellAntallKryss filStiTest |> Seq.toArray

// Antall testkryss
tellAntallKryss filStiTest
|> Seq.filter (fun (k, _, _, _) -> k = 1)
|> Seq.length

// Antall kryss
tellAntallKryss filStiProd
|> Seq.filter (fun (k, _, _, _) -> k = 1)
|> Seq.length

// Antall lengder
tellAntallKryss filStiProd
|> Seq.last
|> fun (_, lengder, _, _) -> lengder

Elixir ❤️

defmodule Day16 do
  def solve(fjord, position \\ %{y: 44, x: 1}, direction \\ :ne, answer \\ 1)
  def solve(_, %{x: x}, _, answer) when x == 3001, do: answer
  def solve(fjord, %{y: y, x: x} = position, direction, answer) do
    if distance_from_land(fjord, position, direction) <= 2 do
      solve(fjord, %{y: y, x: x + 1}, switch_direction(direction), answer + 1)
    else
      solve(fjord, keep_sailing(position, direction), direction, answer)
    end
  end

  def distance_from_land(fjord, %{y: y, x: x}, direction) do
    row =
      fjord
      |> Enum.map(&Enum.at(&1, x))
      |> Enum.join("")

    if direction == :ne do
      String.slice(row, 0, y)
      |> String.replace("#", "")
      |> String.length()
    else
      String.slice(row, y+1, 68)
      |> String.replace("#", "")
      |> String.length()
    end
  end

  def keep_sailing(%{y: y, x: x}, direction) when direction == :ne, do: %{y: y - 1, x: x + 1}
  def keep_sailing(%{y: y, x: x}, direction) when direction == :se, do: %{y: y + 1, x: x + 1}

  def switch_direction(direction) when direction == :ne, do: :se
  def switch_direction(direction) when direction == :se, do: :ne
end

File.read!("fjord.txt")
|> String.split("\n", trim: true)
|> Enum.map(&String.split(&1, "", trim: true))
|> Day16.solve()
|> IO.puts()