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.

Sleit mye med de 20-metrene fra land, samt at hun skulle gå fremover mens hun snur, noe som ga mye feil. Brukte også en del forsøk på å teste off-by-one.
Tegna også visuelt for å se hva faen jeg holdte på med..

<?php
function moveBirte($way) {
    global $birte, $direction, $map, $chDir;
    list($x,$y) = $birte;
    list($dx,$dy) = $direction[$way];
    
    if(count($map) <= $x+1) {
        $map = array_map(function($line) { return implode('', $line); }, array_map(null, ...$map));
        $handle = fopen("data_new.txt", "w");
        foreach($map as $line)
            fwrite($handle, $line."\n");
        fclose($handle);
        echo "<pre>".file_get_contents("data_new.txt");
        die("<h1>$chDir</h1>");
    }
    
    $birte = [$x+$dx,$y+$dy];
    if($x != 1) 
        $map[$x][$y] = ($way != "north" ? '\\' : '/');
    
    if($map[$x][$y+($dy*3)] == "#" || $map[$x+1][$y+($dy*3)] == "#") {
        $chDir++;
        $birte = [$x+1,$y];
        moveBirte(($way == 'north' ? 'south' : 'north'));
    }
    moveBirte($way);
}

$chDir=0;
$birte = [0,0];
$direction = ['north' => [1,  -1], 'south'  => [1, 1]];
$data = file("data.txt");
$data = array_map('str_split', $data);
$map = array_map(null, ...$data);

foreach($map as $x => $field) 
    foreach($field as $y => $sign)
        if($sign == "B") 
            $birte = [$x, $y];
        elseif($sign != "#")
            $map[$x][$y] = " ";
         

moveBirte('north');

edit: Etter å ha lest diskusjonene lengre opp her er jeg sikker på at koden min er feil i forhold til den EGENTLIGE ruten skal kjøre.

Morsom oppgave!

Løste denne med C# og brukte SixLabors.ImageSharp.Drawing til å lage .png.

De fleste som sverger til engelske variabelnavn (og hvem gjør vel ikke det?)

Jeg gjør ikke det. Jeg bruker norsk når det faller naturlig. Som her hvor oppgaveteksten er på norsk. Da er det norsk all the way hele veien.

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()