Skip to content

Instantly share code, notes, and snippets.

@knowitkodekalender knowitkodekalender/2019 Luke 16.md Secret
Last active Dec 17, 2019

Embed
What would you like to do?

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 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.

@amumurst

This comment has been minimized.

Copy link

amumurst commented Dec 16, 2019

Dagens lille rekursive scala løsning. Kløna litt med at man må stoppe dersom man er på vei inn i en rute hvor "land kommer mot deg", altså en odde slik at man må implementere look-ahead til neste iterasjon. Ellers transposer jeg input slik at hver linje er et tverrsnitt av fjorden og rekurser over fjorden. Da kan man tolke hvert tversnitt som en ny start med nye parametere.

object Day16 extends App {
  val file                       = scala.io.Source.fromFile("Day16.txt").getLines().toList
  val transposedInput = file.map(_.padTo(file.head.length, ' ')).reverse.transpose.drop(1)

  def move(fjord: List[List[Char]], bPos: Int, turns: Int): Int = {
    val dir = if(turns%2==0) 1 else -1
    fjord match {
      case head :: next :: rest if head(bPos + dir * 3) == '#' || next(bPos + dir * 3) == '#' => move(next +: rest, bPos, turns + 1)
      case head :: rest => move(rest, bPos + dir, turns)
      case _            => turns
    }
  }

  println(move(transposedInput, transposedInput.head.indexOf('B'), 0))
}
@jonathangjertsen

This comment has been minimized.

Copy link

jonathangjertsen commented Dec 16, 2019

Python

def load_fjord():
    with open("fjord.txt") as file:
        lines = [line[:-1] for line in file.readlines()]

    for y, row in enumerate(lines):
        for x, char in enumerate(row):
            if char == "B":
                return x, y, lines

x, y, lines = load_fjord()
crosses = 1
going_up = True
while x < len(lines[0]):
    if lines[y-3][x] == "#" and going_up:
        going_up = False
        x += 1
        crosses += 1
    elif lines[y+3][x] == "#" and not going_up:
        going_up = True
        x += 1
        crosses += 1
    if going_up:
        y -= 1
    else:
        y += 1
    x += 1
print(crosses)
@joakimwinum

This comment has been minimized.

Copy link

joakimwinum commented Dec 16, 2019

AWK løsning:
awk -f door_16.awk door_16/fjord.txt

BEGIN {
	FS = ""
	north = "north"
	south = "south"
	null = "null"
	direction = north
	count = 1
}

NR == 1 {
	for (i = 2; i <= NF; i++) {
		landDirection[i] = north
	}
}

{
	for (i = 2; i <= NF; i++) {
		switch ($i) {
		case "#":
			land[landDirection[i]][i] = NR
			if (landDirection[i] == south) {
				landDirection[i] = null
			}
			break
		case " ":
			landDirection[i] = south
			break
		case "B":
			boat = NR
			break
		}
	}
}

END {
	y = boat
	for (i = 3; i <= NF; i++) {
		if (direction == north) {
			if (y <= land[north][i] + (2 + 1)) {
				direction = south
				++count
				continue
			}
			y--
		} else if (direction == south) {
			if (y >= land[south][i] - (2 + 1)) {
				direction = north
				++count
				continue
			}
			y++
		}
	}
}

END {
	print count
}
@sondremb

This comment has been minimized.

Copy link

sondremb commented Dec 16, 2019

Sånn passe kompakt Python3

with open('fjord.txt') as f:
    lines = f.readlines()
    fjord = [''.join(l[i] for l in lines) for i in range(len(lines[0])-1)]

turns, dy = 0, -1
y = fjord[1].find('B')

for x in range(len(fjord)):
    if fjord[x][y + dy * 3] == '#':
        turns += 1
        dy *= -1
    else:
        y += dy

print(turns + 1)
@Bullhill

This comment has been minimized.

Copy link

Bullhill commented Dec 16, 2019

Dagens php

Tegner opp kartet der hun har kjørt også

<?php

$file = file_get_contents("fjord.txt");
$map = rotatemap($file);

$goright = false;
$bpos = 0;
$turn = 0;
foreach($map as $l => $line)
{
	if($bpos == 0)
	{
		$bpos = array_search("B", $line);
	}
	elseif($goright)
	{
		$bpos++;
		$map[$l][$bpos] = "\\";
		if($line[$bpos+3] == "#" || $map[$l+1][$bpos+3] == "#")
		{
			$goright = false;
			$bpos++;
			$turn++;
		}
	}
	else
	{
		$bpos--;
		$map[$l][$bpos] = "/";
		if($line[$bpos-3] == "#" || $map[$l+1][$bpos-3] == "#")
		{
			$goright = true;
			$bpos--;
			$turn++;
		}
	}
}


foreach($map as $line)
{
	echo implode($line) . "\n";
	usleep(50000);
}
echo $turn . "\n";


function rotatemap($file)
{
	$lines = explode("\n", $file);
	
	foreach($lines as $l => $line)
	{
		$chars = str_split($line);
		foreach($chars as $c => $char)
		{
			$map[$c][$l] = $char;
		}
	}
	return $map;
	
}

?>
`

https://gist.github.com/Bullhill/9cd170026ded80ac51391c8e1ea0354b
@danieman

This comment has been minimized.

Copy link

danieman commented Dec 16, 2019

Tok en stund før jeg oppdaget i eksempelet at hun bare går rett østover ved kryssing (og ikke alltid enten nordover eller sørover).

with open('fjord.txt') as f:
    fjord = [line.strip('\n') for line in f]

for i, line in enumerate(fjord):
    if 'B' in line:
        b = (line.index('B'), i)
        fjord_length = len(line)

crosses = 1
direction = -1   # -1 for north, 1 for south

while b[0] < fjord_length-1:
    b = (b[0] + 1, b[1] + direction)
    if fjord[b[1]+3*direction][b[0]] == '#':
        b = (b[0]+1, b[1])
        direction *= -1
        crosses += 1

print(crosses)
@lassem

This comment has been minimized.

Copy link

lassem commented Dec 16, 2019

Prøvde meg med noe tuples, men ble ikke så pent som jeg håpet på.

#!/usr/bin/env python3

fjord = open("fjord.txt").readlines()

birte = (-1, -1)
for y in range(0, len(fjord)):
    for x in range(0, len(fjord[y])):
        if fjord[y][x] is 'B':
            birte = (x, y)

def findCrossings(start, delta):
    crossings = 1
    pos = start
    while pos[0] < 3001:
        border = (pos[0] + delta[0], pos[1] + (delta[1] * 3))
        if fjord[border[1]][border[0]] == '#':
            delta = (delta[0], delta[1] * -1)
            pos = (pos[0] + delta[0], pos[1])
            crossings += 1
        else:
            pos = (pos[0] + delta[0], pos[1] + delta[1])

    return crossings

print(f"start -y: {findCrossings(birte, (1, -1))}")
@flogvit

This comment has been minimized.

Copy link

flogvit commented Dec 16, 2019

Rett fram node variant.

let data = require('fs').readFileSync('data/fjord.txt', 'utf8').split(/\n/).map(l => l.split(''));
let pos = {x: 0, y: 0};
let dir = 1;
let count = 1;
data.map((d, y) => data[y].map((d, x) => {
    if (data[y][x] === 'B') pos = {x: x, y: y}
}));

do {
    if (data[pos.y + dir][pos.x + 1] === ' ' &&
        data[pos.y + (dir * 2)][pos.x + 1] === ' ' &&
        data[pos.y + (dir * 3)][pos.x + 1] === ' ') {
        pos.y += dir;
    } else {
        dir *= -1;
        count++;
    }
    pos.x += 1;
} while (pos.x < data[0].length);

console.log(count);
@Sjark

This comment has been minimized.

Copy link

Sjark commented Dec 16, 2019

C#:

var fjord = File.ReadAllLines("Input\\fjord.txt");

var goingNorth = true;
var bloc = (x: -1, y: -1);
var crossings = 1;

for (int y = 0; y < fjord.Length; y++)
{
    for (int x = 0; x < fjord[y].Length; x++)
    {
        if (fjord[y][x] == 'B')
        {
            bloc.x = x;
            bloc.y = y;

            break;
        }
    }

    if (bloc.x != -1)
    {
        break;
    }
}

while (bloc.x != fjord[0].Length)
{
    if (goingNorth && bloc.y - 3 > 0 && fjord[bloc.y - 3][bloc.x] != '#')
    {
        bloc.x += 1;
        bloc.y -= 1;
    }
    else if (!goingNorth && bloc.y + 3 < fjord.Length - 1 && fjord[bloc.y + 3][bloc.x] != '#')
    {
        bloc.x += 1;
        bloc.y += 1;
    }
    else
    {
        crossings += 1;
        goingNorth = !goingNorth;
        bloc.x += 1;
    }
}

Console.WriteLine(crossings);
@Suppen

This comment has been minimized.

Copy link

Suppen commented Dec 16, 2019

Får off-by-one av en eller annen grunn. Mulig det er ren flaks at denne koden nesten funker, da Birte er helt inntil land noen steder. Den gir rett svar på eksempelet.

EDIT: Kilden til off-by-one er funnet. Koden under teller antall ganger hun snur, mens spørsmålet egentlig var hvor mange strekninger hun kjørte. Fikses ved å bytte initiell verdi på crossings fra 0 til 1. Problemet er at da får jeg off-by-one på eksempelet...

Jeg transponerte fjorden for å kunne håndtere den rad for rad istedet for kolonne for kolonne. Den var også vesentlig lettere å printe vertikalt enn horisontalt. Her er JS-kode med visualisering av ruten. En smal sak å porte denne koden til Haskell. Jeg gjør det senere i dag.

"use strict";

const fs = require("fs");
const R = require("ramda");

const WEST = "w";
const EAST = "e";

R.compose(
        console.log.bind(console),
        // Take the answer
        R.nth(2),
        // Start crossing
        ({ x, fjord }) =>
                R.reduce(([x, dir, crossings], row) => {
                        /* Visualize the fjord and the route. This code is not necessary*/
                        R.compose(
                                console.log.bind(console),
                                R.join(""),
                                R.update(x, dir === WEST ? "/" : "\\"),
                                R.split("")
                        )(row);
                        /* End visualization */

                        if (dir === WEST && row[x - 3] !== " ") {
                                crossings++;
                                dir = EAST;
                        } else if (dir === EAST && row[x + 3] !== " ") {
                                crossings++;
                                dir = WEST;
                        } else if (dir === WEST) {
                                x--;
                        } else if (dir === EAST) {
                                x++;
                        }

                        return [x, dir, crossings];
                }, [x, WEST, 0])(fjord),
        // Initialize it
        fjord => {
                // Transpose the fjord for easier reduction
                const transposedFjord = R.compose(
                        R.map(R.join("")),
                        R.transpose
                )(fjord);

                // Find the start position
                const y = R.findIndex(R.includes("B"), transposedFjord);
                const x = R.findIndex(R.equals("B"), transposedFjord[y]);

                // Drop rows before the boat
                const modifiedFjord = R.drop(y, transposedFjord);

                return { x, fjord: modifiedFjord };
        },
        // Parse the file
        R.split("\n"),
        R.trim
)(fs.readFileSync("input.txt", "utf-8"));
@MarcusTL12

This comment has been minimized.

Copy link

MarcusTL12 commented Dec 16, 2019

Ikke bare meg som slet med å se at x-koordinaten økte ved kryssning nei.
Her er julia kode som er tweeket til alle off by one errorer i alle retninger nullet seg ut...

function main()
    startpos = (0, 0)
    
    fjord = open("fjord.txt") do io
        i = 1
        lines = BitArray[]
        for l in eachline(io)
            c = Vector{Char}(l)
            
            for j in 1 : length(c)
                if c[j] == 'B'
                    startpos = (i, j)
                end
            end
            
            push!(lines, BitArray(map(x->x=='#', c)))
            
            i += 1
        end
        hcat(lines...) |> transpose |> copy
    end
    
    speed = -1
    crosses = 1
    h, w = size(fjord)
    
    xpos = startpos[2]
    ypos = startpos[1]
    
    path = falses(h, w)
    
    while xpos < w - 1
        i = 1
        
        while xpos + i <= w && !fjord[ypos + i * speed, xpos + i]
            i += 1
        end
        
        if xpos + i >= w
            break
        end
        
        if i <= 3
            speed *= -1
            crosses += 1
            xpos += 1
        end
        
        xpos += 1
        ypos += speed
    end
    
    crosses
end
@BobuSumisu

This comment has been minimized.

Copy link

BobuSumisu commented Dec 16, 2019

Endte også opp med off-by-one jf. eksemplet.

Antar det er fordi jeg egentlig teller antall ganger hun snur og i eksemplet så snur hun på aller siste x-koordinat?

Oh well.

@bobcat4

This comment has been minimized.

Copy link

bobcat4 commented Dec 16, 2019

Sitter med samme følelsen av flaks som @Suppen, skjønt jeg fikk rett svar.

birte

Her er det vel strengt tatt mindre enn 20 meter fra land. Birte burde ha vært los ombord på KNM «Helge Ingstad». :)

birte2

Her er det ganske åpenbart. Hadde denne odden vært 10 meter lenger sør, hadde det blitt havari. Enten er det jeg som har hatt flaks, eller så er oppgaven litt "ullen"...

Edit: Jeg så ikke siste del av denne: "For å krysse færrest mulige ganger snur hun når hun er 20 meter fra land (nord/sør)." :)
Edit2: Og jeg fant en bug, Birte beveger seg 3.3m rett øst helt i starten. Det er litt synd at slike oppgaver kan løses med buggy kode...

Koden er ikke noe å skryte av, men kjøretiden ble nette 540 µs

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUFFSIZE 201134

void luke16 ()
{
    char *buffer = malloc(BUFFSIZE);
    FILE *f = fopen("fjord.txt", "rb");
    fread(buffer, BUFFSIZE, 1, f);
    fclose(f);

    int b = 44; // Birte
    int dir = -1;
    int pdir = 0;
    int cnt = 0;

    for(int x=2; x<3001; x++) {
        if (dir == -1) {
            if (buffer[((b-3)*3002)+x] == '#') dir = -dir;
        }
        else {
            if (buffer[(b+3)*3002+x] == '#') dir = -dir;
        }
        if (pdir != dir) {
            cnt++;
            pdir = dir;
        }
        else b += dir;
    }
    free(buffer);
    printf("%d\n", cnt);
}
@stianeikeland

This comment has been minimized.

Copy link

stianeikeland commented Dec 16, 2019

Enig @danieman, var uklart (ut fra teksten) at en krysning tok "to x-ruter".

@AndersSteenNilsen

This comment has been minimized.

Copy link

AndersSteenNilsen commented Dec 16, 2019

Heldigvis blir det samme svar om en sjekker (x+1, y+-3) eller (x, y+-3).
ans
PS Om hver rute er 10m2 vil sidene bli 3.33 m og en burde ha sjekket 6 ruter nord/sør ?

@AndersSteenNilsen

This comment has been minimized.

Copy link

AndersSteenNilsen commented Dec 16, 2019

Heldigvis blir det samme svar om en sjekker (x+1, y+-3) eller (x, y+-3).
ans
PS Om hver rute er 10m2 vil sidene bli 3.33 m og en burde ha sjekket 6 ruter nord/sør ?

PPS: Om Berit begynner sørøst vil hun kun trenge 116 krysninger.
PPPS: ""For å krysse færrest mulige ganger"" -> Dette implementerer at Birte er interessert i å krysse kortest mulig ganger ved å snu når hun er 20 meter fra land. Dette gjelder vel ikke alltid??

@lassem

This comment has been minimized.

Copy link

lassem commented Dec 16, 2019

Kosten for snu er jo 0 slik det står nå. X + 1 uansett. Oppgaven hadde kanskje dratt nytte av at snu-kostnaden var var 1:

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

Eller nei.. Blir jo ikke noe særlig mer spennende av den grunn.

@knowitkodekalender

This comment has been minimized.

Copy link
Owner Author

knowitkodekalender commented Dec 16, 2019

Takk for tilbakemeldinger. Vi har endret oppgaveteksten og eksempelet nå.

@Suppen

This comment has been minimized.

Copy link

Suppen commented Dec 16, 2019

Fløgende tekst er lagt til:
"OBS! Antall kryssinger er definert som antall strekninger hun seiler, ikke antall ganger hun snur."

Der kommer nok off-by-one-feilen min fra. Jeg telte antall ganger hun snudde. Det gjør meg også sikker på at det ikke bare er flaks som gjør at koden min funker. Jeg trodde først at jeg fikk båten til å snu på helt feil steder, og det tilfeldigvis ble nesten like mange snuinger som oppgaven var ute etter.

@flogvit

This comment has been minimized.

Copy link

flogvit commented Dec 16, 2019

Måtte prøve meg på en optimalisert versjon i node/javascript. 862 µs for selve programmet inkludert innlesing av data (etter lasting av node) er jo ikke så dårlig.

console.time('programtime');
let data = require('fs').readFileSync('data/fjord.txt');
let xlen = data.indexOf("\n")+1;
let xlen1 = xlen-1;
let pos = data.indexOf("B");
let dir = -1;
let count = 0;

for(;pos%xlen!==xlen1;) {
    pos++;
    if (data[pos+(xlen*dir)]===32 &&
        data[pos+(xlen*dir*2)]===32 &&
        data[pos+(xlen*dir*3)]===32) {
        pos += xlen*dir;
    } else {
        dir = -dir;
        count++;
    }
}
console.timeEnd('programtime');
console.log(count);
 $ time node test.js 
programtime: 0.862ms
117

real    0m0.046s
user    0m0.035s
sys     0m0.010s
@terjew

This comment has been minimized.

Copy link

terjew commented Dec 16, 2019

Selv etter omskrivingen av oppgaven synes jeg den er litt hårete formulert.

"Hun må snu når hun er 20 meter fra land" impliserer at hun aldri vil komme nærmere enn 20 meter fra land i N/S, men det gjør hun jo. Man kan også ledes til å tro at det skal tolkes "hun må snu tidsnok til å aldri komme nærmere enn 20 meter fra land i N/S", men det ga såvidt jeg kunne se feil svar.

Hvordan selve snuoperasjonen gjennomføres var heller ikke så godt forklart, og gir vel heller ikke særlig mening i virkeligheten? Når man krysser antar jeg at det er noe man gjør fordi man seiler mot vinden, og i forbindelse med kryssing bør man jo strengt tatt blåse bakover, ikke fremover.

Uansett, ble god trening i å forsøke å få tilsynelatende motstridende krav implementert samtidig, og når sant skal sies brukte jeg vel mer tid på visualiseringen enn på implementasjonen (windows-konsollet er tregt...)

Visualisering i konsoll

@aude

This comment has been minimized.

Copy link

aude commented Dec 16, 2019

Go (0.01s)

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"log"
	"os"
)

func usage() string {
	return "usage: input | " + os.Args[0]
}

type Pos struct {
	X, Y int
}

type Direction bool

const Up Direction = true
const Down Direction = false

type Fjord [][]byte

func (fjord Fjord) String() string {
	s := ""
	for _, line := range fjord {
		s += string(line) + "\n"
	}
	return s
}

func (fjord Fjord) At(pos Pos) *byte {
	return &fjord[pos.Y][pos.X]
}

func sail(fjord Fjord) Fjord {
	// find start position
	var pos Pos
	for pos.X, pos.Y = 1, 0; pos.Y < len(fjord); pos.Y++ {
		if *fjord.At(pos) == 'B' {
			break
		}
	}

	direction := Up
	for pos.X < len(fjord[0])-1 {
		if direction == Up {
			if *fjord.At(Pos{pos.X, pos.Y - 3}) == ' ' {
				pos = Pos{pos.X + 1, pos.Y - 1}
				*fjord.At(pos) = '/'
			} else {
				pos = Pos{pos.X + 1, pos.Y}
				*fjord.At(pos) = '\\'
				direction = Down
			}
		} else {
			if *fjord.At(Pos{pos.X, pos.Y + 3}) == ' ' {
				pos = Pos{pos.X + 1, pos.Y + 1}
				*fjord.At(pos) = '\\'
			} else {
				pos = Pos{pos.X + 1, pos.Y}
				*fjord.At(pos) = '/'
				direction = Up
			}
		}
	}

	return fjord
}

func crossings(fjord Fjord) int {
	crossings := 1
	for _, line := range fjord {
		crossings += bytes.Count(line, []byte(`/\`))
		crossings += bytes.Count(line, []byte(`\/`))
	}
	return crossings
}

func main() {
	var fjord Fjord

	reader := bufio.NewReader(os.Stdin)
	for {
		bytes, err := reader.ReadBytes('\n')
		if err == io.EOF {
			break
		}
		if err != nil {
			log.Println(err)
			fmt.Fprintln(os.Stderr, usage())
			os.Exit(1)
		}
		// remove trailing newline
		bytes = bytes[:len(bytes)-1]
		fjord = append(fjord, bytes)
	}

	// fmt.Printf("%v", fjord)
	// fmt.Printf("%v", sail(fjord))
	fmt.Println(crossings(sail(fjord)))
}
@AnLof

This comment has been minimized.

Copy link

AnLof commented Dec 16, 2019

Sailing home for Christmas!
SailingHomeForChristmas

@sat90

This comment has been minimized.

Copy link

sat90 commented Dec 16, 2019

måtte trikse litt her og der men ordnet seg til slutt:

data = {}


def loadData():
    GOAL = 0
    XB = 0
    YB = 0
    with open("luke16.txt") as file:
        for y, line in enumerate(file):
            for x, c in enumerate(line):
                if c == " ":
                    data[(x, y)] = " "
                if c == "#":
                    data[(x, y)] = "#"
                if c == "B":
                    XB = x
                    YB = y
                if x > GOAL:
                    GOAL = x
    return GOAL, XB, YB


def findCrosses(GOAL, XB, YB):
    crosses = 1
    while True:
        while True:
            XB += 1
            YB -= 1
            if XB == GOAL-1:
                return crosses
            if data[(XB, YB-3)] == "#":
                XB += 1
                crosses += 1
                break
        while True:
            XB += 1
            YB += 1
            if XB == GOAL-1:
                return crosses
            if data[(XB, YB+3)] == "#":
                XB += 1
                crosses += 1
                break


GOAL, XB, YB = loadData()
print(findCrosses(GOAL, XB, YB))
@Runebjo

This comment has been minimized.

Copy link

Runebjo commented Dec 16, 2019

JavaScript:

const fs = require('fs');

fs.readFile('fjord.txt', 'utf8', (err, content) => {
    let lines = content.split('\n');
    let currentY = lines.findIndex(l => l.includes('B'));
    let currentX = lines[currentY].indexOf('B');
    let crosses = 1;
    let isUp = true;

    function shouldCross() {
        let nextX = currentX + 1;
        let nextY = isUp ? currentY - 3 : currentY + 3;
        let nextChar = lines[nextY][nextX] === '#';
        if (nextChar) return true;
        return false;
    }

    while (currentX < lines[currentY].length) {
        if (shouldCross()) {
            isUp = !isUp;
            crosses++;
        }
        else {
            currentY += isUp ? -1 : 1;
        }
        currentX += 1;
    }
    console.log(crosses);
})
@bobcat4

This comment has been minimized.

Copy link

bobcat4 commented Dec 16, 2019

Litt morsomt å lese koden her. De fleste som sverger til engelske variabelnavn (og hvem gjør vel ikke det?), har oversatt "krysse" til "cross", noe som i utgangspunktet er naturlig. Jeg var innom samme tanke, men fikk en følelse av at det var feil. Sjø- og seileuttrykk er ofte noe helt annet enn hva man tror. :-)

Å krysse er "Tacking or coming about" på engelsk, fant jeg ut via Wikipedia.

Og at det er gresk (og vel så det) beskriver denne setningen fra norsk Wikipedia godt:

"For å krysse og komme fram dit man ønsker må man snu båten fra å seile på den ene halseren, til den andre. Dette kalles å gå over stag eller å slå. Dette gjøres ved å styre båten opp mot vindøyet, gjennom vindøyet, og ned på nå hals ved hjelp av båtens fart før manøvreringen begynte."

Det skal ikke være enkelt...

@iamxerc

This comment has been minimized.

Copy link

iamxerc commented Dec 16, 2019

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.

@anderaus

This comment has been minimized.

Copy link

anderaus commented Dec 16, 2019

Morsom oppgave!

result

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

@jostyposty

This comment has been minimized.

Copy link

jostyposty commented Dec 16, 2019

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.

@christianfosli

This comment has been minimized.

Copy link

christianfosli commented Dec 16, 2019

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

@Stian108

This comment has been minimized.

Copy link

Stian108 commented Dec 16, 2019

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
@teilin

This comment has been minimized.

Copy link

teilin commented Dec 16, 2019

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)
}
@mikaello

This comment has been minimized.

Copy link

mikaello commented Dec 16, 2019

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;
@Aha43

This comment has been minimized.

Copy link

Aha43 commented Dec 16, 2019

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;
    }
}
@matslindh

This comment has been minimized.

Copy link

matslindh commented Dec 16, 2019

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))
@hakonrossebo

This comment has been minimized.

Copy link

hakonrossebo commented Dec 16, 2019

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
@gunnar2k

This comment has been minimized.

Copy link

gunnar2k commented Dec 16, 2019

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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.