AoC 2022 - slog

Day 12

S -> E๋กœ ์ƒ,ํ•˜,์ขŒ,์šฐ ํ•œ์นธ์”ฉ ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๋งต์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์‚ฐ๊ธธ์€ ๋†’๋‚ฎ์ด๊ฐ€ ์žˆ์–ด์„œ ๊ฐ€์žฅ ๋‚ฎ์€ a์™€ ๊ฐ€์žฅ ๋†’์€ z๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ์Šต๋‹ˆ๋‹ค. ์œ„๋กœ ๋†’์€ ๊ณณ์œผ๋กœ ์˜ฌ๋ผ๊ฐˆ ๋•Œ๋Š” +1 ์”ฉ์˜ ์ฐจ์ด ๊ฒฝ๋กœ๋งŒ ๊ฐ€๋Šฅํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด a โ†’ b, o โ†’ p ์‹์ž…๋‹ˆ๋‹ค. (๋†’๋‚ฎ์ด๊ฐ€ ๊ฐ™๊ฑฐ๋‚˜ ๋‚ฎ์€ ๊ฒฝ์šฐ๋Š” ์ œํ•œ์ด ์—†์Šต๋‹ˆ๋‹ค.)

AoC์˜ ๋‹ค๋ฅธ ๋ฌธ์ œ๋“ค ์ฒ˜๋Ÿผ ์ž‘์€ ์‚ฌ์ด์ฆˆ์˜ ์ž…๋ ฅ์„ ํ†ตํ•ด ๊ตฌํ˜„์„ ๊ฒ€์ฆํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

์ž‘์€ ๋งต์˜ ๊ฒฝ์šฐ ์งง์€ ์‹œ๊ฐ„์— ๋‹ต์„ ๊ตฌํ–ˆ๋Š”๋ฐ ์‹ค์ œ ์ž…๋ ฅ ๋งต์˜ ๊ฒฝ์šฐ 95x41 ์‚ฌ์ด์ฆˆ๋กœ ๋‹ค์–‘ํ•œ ๊ณ ๋ ค ์‚ฌํ•ญ์ด ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๊ฐ„๋‹จํ•œ ํƒ์ƒ‰ ๋ฐฉ๋ฒ•์œผ๋กœ๋Š” ์‹œ๊ฐ„์ด ์ƒ๋‹นํžˆ ์†Œ์š”๋ฉ๋‹ˆ๋‹ค.


๋„“์ด ์šฐ์„  ํƒ์ƒ‰์„ ์ด์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค.

public static string Solve1(string input)
{
    var mountain = Mountain.Parse(input, false);

    var directions = new (int X, int Y, char Mark)[] { (1, 0, '>'), (0, 1, 'v'), (0, -1, '^'), (-1, 0, '<') };
    var result = MoveTrail(mountain, mountain.StartPos, directions);
    if (result is null)
        throw new InvalidOperationException();

    Console.WriteLine(result.M);

    return result.GetAllMarkPositions()
        .Count(c => c is '^' or '>' or 'v' or '<')
        .ToString();

    static Mountain? MoveTrail(Mountain mountain, (int X, int Y) cp, (int X, int Y, char Mark)[] directions)
    {
        var visited = new Dictionary<(int X, int Y), bool>
        {
            { cp, true }
        };
        var stack = new Queue<(Mountain mountain, (int X, int Y) cp)>();
        stack.Enqueue((mountain, cp));

        while (stack.Count > 0)
        {
            var count = stack.Count;
            foreach (var _ in Enumerable.Range(1, count))
            {
                (mountain, cp) = stack.Dequeue();

                foreach (var direction in directions)
                {
                    var bResult = mountain.FindTrail(cp, (direction.X, direction.Y));
                    (int X, int Y) mv = (cp.X + direction.X, cp.Y + direction.Y);
                    if (bResult is true && visited.ContainsKey(mv) is false)
                    {
                        var newMountain = new Mountain(mountain);
                        newMountain.M[cp.X, cp.Y] = direction.Mark;

                        if (newMountain[mv.X, mv.Y] == newMountain.EndMark)
                            return newMountain;

                        visited[mv] = true;
                        stack.Enqueue((newMountain, mv));
                    }
                }
            }
        }

        return null;
    }
}

public static string Solve2(string input)
{
    var mountain = Mountain.Parse(input, true);

    var directions = new (int X, int Y, char Mark)[] { (1, 0, '>'), (0, 1, 'v'), (0, -1, '^'), (-1, 0, '<') };

    var result = MoveTrail(mountain, mountain.StartPos, directions);
    if (result is null)
        throw new InvalidOperationException();

    Console.WriteLine(result.M);

    return result.GetAllMarkPositions()
        .Count(c => c is '^' or '>' or 'v' or '<')
        .ToString();

    static Mountain? MoveTrail(Mountain mountain, (int X, int Y) cp, (int X, int Y, char Mark)[] directions)
    {
        var visited = new Dictionary<(int X, int Y), bool>
        {
            { cp, true }
        };
        var stack = new Queue<(Mountain mountain, (int X, int Y) cp)>();
        stack.Enqueue((mountain, cp));

        while (stack.Count > 0)
        {
            var count = stack.Count;
            foreach (var _ in Enumerable.Range(1, count))
            {
                (mountain, cp) = stack.Dequeue();

                foreach (var direction in directions)
                {
                    var bResult = mountain.FindTrail(cp, (direction.X, direction.Y));
                    (int X, int Y) mv = (cp.X + direction.X, cp.Y + direction.Y);
                    if (bResult is true && visited.ContainsKey(mv) is false)
                    {
                        var newMountain = new Mountain(mountain);
                        newMountain.M[cp.X, cp.Y] = direction.Mark;

                        if (newMountain[mv.X, mv.Y] == newMountain.EndMark)
                            return newMountain;

                        visited[mv] = true;
                        stack.Enqueue((newMountain, mv));
                    }
                }
            }
        }

        return null;
    }
}

class Mountain
{
    private readonly string _grid;
    private readonly Mark _mark;
    private char _endMark = 'E';
    private bool _isReverse;

    public char EndMark => _endMark;

    public int Width { get; }
    public int Height { get; }

    public int Left => 0;
    public int Top => 0;
    public int Right => Width - 1;
    public int Bottom => Height - 1;

    public (int X, int Y) StartPos { get; }
    public (int X , int Y) EndPos { get; }
            


    private Mountain(string input, bool isReverse)
    {
        Height = input.Count(x => x is '\n') + 1;
        _grid = input.Replace(Environment.NewLine, "");
        Width = _grid.Length / Height;
        _mark = new Mark(this);

        var startPosition = _grid.IndexOf('S');
        StartPos = (startPosition % Width, startPosition / Width);
        var endPosition = _grid.IndexOf('E');
        EndPos = (endPosition % Width, endPosition / Width);

        _mark[StartPos.X, StartPos.Y] = 'S';
        _mark[EndPos.X, EndPos.Y] = 'E';

        _isReverse = isReverse;
        if (isReverse is true)
        {
            _endMark = 'a';
            StartPos = EndPos;
        }
    }

    public Mountain(Mountain grid)
    {
        Width = grid.Width;
        Height = grid.Height;
        _grid = grid._grid;
        _mark = new Mark(grid._mark);
        _endMark = grid._endMark;
        _isReverse = grid._isReverse;
    }

    public Mark M => _mark;

    public char this[int x, int y]
    {
        get
        {
            if (x < Left || x > Right || y < Top || y > Bottom)
                return '#';

            return _grid[y * Width + x];
        }
    }

    public IEnumerable<char> GetAllMarkPositions() => M.GetAllPositions();


    public bool FindTrail((int X, int Y) cp, (int X, int Y) tp)
    {
        var currentTrail = this[cp.X, cp.Y];
        var findTrail = currentTrail switch
        {
            'E' => 'z',
            'S' => 'a',
            'z' => 'E',
            _ => _isReverse is false ? (char)(currentTrail + 1) : (char)(currentTrail - 1),
        };
        (tp.X, tp.Y) = (cp.X + tp.X, cp.Y + tp.Y);
        var nextTrail = this[tp.X, tp.Y];

        if (nextTrail is '#')
            return false;

        if (M[tp.X, tp.Y] is not '.' && M[tp.X, tp.Y] != _endMark)
            return false;

        if (_isReverse is false)
        {
            if (nextTrail == findTrail || (nextTrail != _endMark && nextTrail <= currentTrail))
                return true;
        }
        else
        {
            if (nextTrail == findTrail || (nextTrail != _endMark && nextTrail >= currentTrail))
                return true;
        }

        return false;
    }

    public override string ToString()
    {
        var sb = new StringBuilder();
        foreach (var (c, i) in _grid.Select((c, i) => (c, i)))
        {
            sb.Append(c);
            if ((i + 1) % Width is 0)
                sb.AppendLine();
        }
                
        return sb.ToString();
    }

    public static Mountain Parse(string input, bool isReverse) => new(input, isReverse);

    public class Mark
    {
        private readonly char[] _mark;
        private readonly int _width;

        public Mark(Mountain mountain)
        {
            _width = mountain.Width;
            _mark = Enumerable.Repeat('.', mountain._grid.Length).ToArray();
        }

        public Mark(Mark mark)
        {
            _width = mark._width;
            _mark = mark._mark.ToArray();
        }

        public char this[int x, int y]
        {
            get => _mark[y * _width + x];
            set => _mark[y * _width + x] = value;
        }

        public IEnumerable<char> GetAllPositions() => _mark;

        public override string ToString()
        {
            var sb = new StringBuilder();
            foreach (var (c, i) in _mark.Select((c, i) => (c, i)))
            {
                sb.Append(c);
                if ((i + 1) % _width is 0)
                    sb.AppendLine();
            }

            return sb.ToString();
        }
    }
}

๋งˆ์Œ์— ๋“œ๋Š” ์ฝ”๋“œ๋Š” ์•„๋‹Œ๋ฐโ€ฆ ์‹œ๊ฐ„ ๊ด€๊ณ„ ์ƒ ๋„˜์–ด๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค;
์ด์ œ๋Š” ๋‚œ์ด๋„๊ฐ€ ๋†’์•„์ ธ์„œ ํ•˜๋ฃจ์— ํ•˜๋‚˜๋งŒ ํ’€์–ด์•ผ๊ฒ ์Šต๋‹ˆ๋‹ค.

1 Like

Day 13

์ผ๋ฐ˜: ํŒจํ‚ท์„ ๋ถ„์„ํ•ด์„œ ์˜ฌ๋ฐ”๋ฅธ ์ˆœ์„œ๋กœ ๋œ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
์‹ฌํ™”: [[2]], [[6]] ํŒจํ‚ท์„ ์ถ”๊ฐ€ํ•ด์„œ ์˜ฌ๋ฐ”๋ฅธ ์ˆœ์„œ๋กœ ์ •๋ ฌํ•œ ํ›„ ์ด ํŒจํ‚ท๋“ค์˜ ์œ„์น˜๋ฅผ ๊ณฑํ•œ ๊ฐ’์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

ํ…Œ์ŠคํŠธ๋ฅผ ์œ„ํ•œ ํŒจํ‚ท์€ ์•„๋ž˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค. ํŒจํ‚ท์€ ๋ชฉ๋ก๊ณผ ์ค‘์ฒฉ๋  ์ˆ˜ ์žˆ๋Š” ํ•ญ๋ชฉ์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์œผ๋ฏ€๋กœ ๋‚˜๋ฆ„์˜ ๊ตฌ๋ฌธ ๋ถ„์„์„ ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]

[7,7,7,7]
[7,7,7]

[]
[3]

[[[]]]
[[]]

[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]

์ €๋Š” ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ์œ„ํ•œ ๊ฒƒ์ด๋ฏ€๋กœ ๊ฐ„๋‹จํ•˜๊ฒŒ ๊ตฌํ˜„ํ•˜์˜€์Šต๋‹ˆ๋‹ค.

public static string Solve1(string input)
{
    var items = input.Split(Environment.NewLine)
        .Chunk(3)
        .Select(x => (Left: Packet.Parse(x[0]), Right: Packet.Parse(x[1])))
        .ToArray();

    //foreach (var item in items)
    //{
    //    Console.WriteLine(item.Left);
    //    Console.WriteLine(item.Right);
    //    Console.WriteLine();
    //}

    var sum = items
        .Select((x, i) => (Number: i + 1, Item: x))
        .Where(x => x.Item.Left.Compare(x.Item.Right) is 1)
        .Sum(x => x.Number);

    return sum.ToString();
}

public static string Solve2(string input)
{
    var items = input.Split(Environment.NewLine, StringSplitOptions.TrimEntries)
        .Where(x => x is not "")
        .Concat(new[] { "[[2]]", "[[6]]" })
        .Select(x => Packet.Parse(x))
        .OrderBy(x => x).ToArray();

    var sum = items
        .Select((x, i) => (x, Number: i + 1))
        .Where(x => x.x.ToString() is "[[2]]" or "[[6]]")
        .Aggregate(1, (mul, x) => mul * x.Number);

    return sum.ToString();
}


class Packet : IComparable<Packet>
{
    readonly GroupElement _group;

    private Packet(GroupElement group) => _group = group;

    public static Packet Parse(string input)
    {
        var packet = new Packet((GroupElement)GroupElement.Parse(input).Element);
        return packet;
    }

    public int Compare(Packet another) => _group.Compare(another._group);
    public int CompareTo(Packet? other) => other!.Compare(this);

    public override string ToString() => _group.ToString();
}

abstract class Element
{
    public static (Element Element, int EndPos) Parse(ReadOnlySpan<char> input)
    {
        var result = input[0] switch
        {
            >= '0' and <= '9' => NumberElement.Parse(input),
            '[' => GroupElement.Parse(input),
            _ => throw new InvalidOperationException()
        };

        return result;
    }

    public abstract int Compare(Element element);
}
class NumberElement : Element
{
    public int Value { get; }

    public NumberElement(int value) => Value = value;

    public static new (Element Element, int EndPos) Parse(ReadOnlySpan<char> input)
    {
        var pos = 0;
        while (pos < input.Length)
        {
            if (char.IsNumber(input[pos]) is false)
                break;

            pos++;
        }

        return (new NumberElement(int.Parse(input.Slice(0, pos))), pos);
    }

    public override string ToString() => Value.ToString();

    public override int Compare(Element element)
    {
        if (element is GroupElement groupElement)
            return new GroupElement(this).Compare(groupElement);

        if (element is NumberElement numberElement)
        {
            if (Value < numberElement.Value)
                return 1;
            if (Value > numberElement.Value)
                return -1;
            return 0;
        }

        throw new InvalidOperationException();
    }
}
class GroupElement : Element
{
    public Element[] Elements { get; }

    public GroupElement(Element[] elements) => Elements = elements;

    public GroupElement(Element element) => Elements = new[] { element };

    public static new (Element Element, int EndPos) Parse(ReadOnlySpan<char> input)
    {
        if (input[0] is not '[')
            throw new InvalidOperationException();
        if (input[1] is ']')
            return (new GroupElement(new Element[0]), 2);

        var elements = new List<Element>();
        var (startPos, endPos) = (1, 1);
        while (endPos < input.Length)
        {
            if (input[startPos] is ',')
            {
                endPos++;
                startPos = endPos;
                continue;
            }

            if (input[startPos] is ']')
            {
                endPos++;
                break;
            }

            (var element, endPos) = Element.Parse(input.Slice(startPos));
            elements.Add(element);
            endPos += startPos;
            startPos = endPos;
        }

        return (new GroupElement(elements.ToArray()), endPos);
    }

    public override int Compare(Element another)
    {
        if (another is NumberElement numberElement)
            return Compare(new GroupElement(numberElement));

        if (another is GroupElement groupElement)
        {
            foreach (var (left, right) in Elements.Zip(groupElement.Elements))
            {
                var result = left.Compare(right);
                if (result is not 0)
                    return result;
            }

            // ๊ฐ™์„ ๊ฒฝ์šฐ ๊ฒฝ์šฐ ์›์†Œ ๊ฐฏ์ˆ˜๋กœ ํŒ์ •ํ•œ๋‹ค.
            if (Elements.Length < groupElement.Elements.Length)
                return 1;
            else if (Elements.Length > groupElement.Elements.Length)
                return -1;

            return 0;
        }

        throw new InvalidOperationException();
    }

    public sealed override string ToString() => $"[{string.Join(",", (IEnumerable<Element>)Elements)}]";
}
2 Likes

์ •๋ จ๋˜์ง€ ์•Š์€ ์ฝ”๋“œ๋ฅผ ๋…ธ์ถœํ•˜๋Š” ๊ฒƒ์€ ๋ถ€๋„๋Ÿฌ์›€์„ ์ด๊ฒจ๋‚ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ž˜๋ชป๋œ ๋˜๋Š” ์ข€ ๋” ๋‚˜์€ ๋ฐฉ๋ฒ•์„ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด๋‹ˆ๋งŒํผ ์ฝ”๋“œ๋ฅผ ๋ณด์‹œ๊ณ  ์กฐ์–ธ์„ ํ•ด์ฃผ๊ธธ ๋ถ€ํƒ๋“œ๋ ค์š”.

4 Likes

๋‹ค๋ฅธ ๋ถ„๋“ค์˜ ์ฝ”๋“œ๊ฐ€ ๊ถ๊ธˆํ•ฉ๋‹ˆ๋‹ค. ๋ถ„๋ช…ํžˆ ๋น„์Šทํ•˜์ง€ ์•Š์œผ๋ฆฌ๋ผ ํ™•์‹ ํ•ฉ๋‹ˆ๋‹ค.

์—”์ ค๋ผ๋‹˜์˜ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค. ์ •๊ทœ์‹์„ ์‚ฌ์šฉํ•˜์…จ๊ตฐ์š”.

๋งˆํฌํžˆ์Šค๋‹˜์˜ ์ฝ”๋“œ์ž…๋‹ˆ๋‹ค. ์—‡, ์ €์˜ ์ฝ”๋“œ๋ž‘ ์œ ์‚ฌํ•ฉ๋‹ˆ๋‹ค.

1 Like

Day 14

๋‹ค์Œ์˜ ์ž…๋ ฅ ์ •๋ณด๋ฅผ ์ด์šฉํ•ด

498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9

์•”์„์„ ๊ทธ๋ฆฌ๊ณ  ๋ชจ๋ž˜๋ฅผ ๋–จ์–ด๋œจ๋ ค ๋ฌดํ•œํžˆ ๋–จ์–ด์ง€๋Š” ๋ชจ๋ž˜๊ฐ€ ๋ฐœ๊ฒฌ๋  ๋•Œ๊นŒ์ง€์˜ ๋–จ์–ด์ง„ ๋ชจ๋ž˜์˜ ๊ฐฏ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

์œ„์˜ ์ž…๋ ฅ๊ฐ’์œผ๋กœ ์•„๋ž˜์˜ ๊ทธ๋ฆผ์ด ๊ทธ๋ ค์ง‘๋‹ˆ๋‹ค.

image

์‹ค์ œ ๋ฌธ์ œ์˜ ์ž…๋ ฅ์œผ๋กœ ๊ทธ๋ ค์ง€๋Š” ๊ทธ๋ฆผ์ž…๋‹ˆ๋‹ค.

image

๋ชจ๋ž˜๊ฐ€ ํ•œ์ฐธ ๋–จ์–ด์ง€๊ฒ ๊ตฐ์š”;

2 Likes

์ €์—๊ฒŒ๋Š” ์ ์ ˆํ•œ ๋‚œ์ด๋„์™€ ํฅ๋ฏธ๋ฅผ ์ฃผ๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

์ผ๋ฐ˜ ๋ฌธ์ œ๋Š” ๋ชจ๋ž˜๊ฐ€ ๋ฌดํ•œํžˆ ๋–จ์–ด์ง€๋Š” ์œ„์น˜๊นŒ์ง€ ์Œ“์ธ ๋ชจ๋ž˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ ํ•ฉ๋‹ˆ๋‹คโ€ฆ
์‹ฌํ™” ๋ฌธ์ œ๋Š” ๋งˆ์ง€๋ง‰ ์•”์„์˜ +2 ์œ„์น˜์— ์•”์„๋ฒฝ์ด ์žˆ๋‹ค๊ณ  ์น˜๊ณ  ๋” ์ด์ƒ ๋ชจ๋ž˜๊ฐ€ ์Œ“์ด์ง€ ์•Š๋Š” ์ด ๋ชจ๋ž˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค.

| ์ผ๋ฐ˜

| ์‹ฌํ™”
image

์•ฝ๊ฐ„์˜ ์‹œํ–‰์ฐฉ์˜ค๋Š” ์ฒซ๋ฒˆ์งธ ๋ฌธ์ œ๋Š” ๊ทธ๋ฆฌ๋“œ์˜ ์‚ฌ์ด์ฆˆ๊ฐ€ ๋ณ€ํ•˜์ง€ ์•Š๋Š”๋ฐ ๋‘๋ฒˆ์งธ ์‹ฌํ™” ๋ฌธ์ œ๋Š” ๊ทธ๋ ‡์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ํ•ด์„œ ์‚ฌ์ด์ฆˆ๊ฐ€ ๋ณ€๊ฒฝ๋  ์ˆ˜ ์žˆ๋„๋ก ๋‹ค์†Œ ์„ฑ๋Šฅ ํ•˜๋ฝ์„ ๊ฐ์ˆ˜ํ•˜๊ณ  char[] -> Dictionary<(int, int), char>๋กœ ๋ฐ”๊พธ์—ˆ์Šต๋‹ˆ๋‹ค.

| ์†Œ์Šค์ฝ”๋“œ

1 Like

Day 15

์„ผ์„œ์™€ ์„ผ์„œ๊ฐ€ ๊ฐ์ง€๋œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋น„์ฝ˜์˜ ์ขŒํ‘œ๋ฅผ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›๊ณ ,

Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3

ํŠน์ • y ์ขŒํ‘œ์—์„œ (์—ฌ๊ธฐ์„œ๋Š” 10) ๊ฐ์ง€ํ•œ ๋น„์ฝ˜์ด ์—†๋Š” ์œ„์น˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„œ๋Š” 26๊ฐœ๊ฐ€ ๋‹ต์ž…๋‹ˆ๋‹ค.

                 1    1    2    2
       0    5    0    5    0    5
 9 ...#########################...
10 ..####B######################..
11 .###S#############.###########.

์ด๋Ÿฐ ๋ฌธ์ œ๋Š” ๋‹ค์Œ ์ฒ˜๋Ÿผ ๊ทธ๋ ค๊ฐ€๋ฉด์„œ ๊ทธ๋ ค์ง„ ๊ฒฐ๊ณผ๋กœ ๋‹ต์„ ์ฐพ๋Š”๊ฒŒ ์ข‹์Šต๋‹ˆ๋‹ค. ์ž…๋ ฅ์„ ์ขŒํ‘œ์— ์ฐ๊ณ 

               1    1    2    2
     0    5    0    5    0    5
 0 ....S.......................
 1 ......................S.....
 2 ...............S............
 3 ................SB..........
 4 ............................
 5 ............................
 6 ............................
 7 ..........S.......S.........
 8 ............................
 9 ............................
10 ....B.......................
11 ..S.........................
12 ............................
13 ............................
14 ..............S.......S.....
15 B...........................
16 ...........SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....

๊ฐ์ง€๋œ ๋น„์ฝ˜์ด ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋น„์ฝ˜์ด๋ฏ€๋กœ ๊ทธ ์˜์—ญ์€ ๊ทธ ๋น„์ฝ˜ ์ด์™ธ์— ๋‹ค๋ฅธ ๋น„์ฝ˜์ด ์—†์Œ์„ '#'๋กœ ์ฒดํฌ๋ฅผ ํ•ฉ๋‹ˆ๋‹ค.

               1    1    2    2
     0    5    0    5    0    5
-2 ..........#.................
-1 .........###................
 0 ....S...#####...............
 1 .......#######........S.....
 2 ......#########S............
 3 .....###########SB..........
 4 ....#############...........
 5 ...###############..........
 6 ..#################.........
 7 .#########S#######S#........
 8 ..#################.........
 9 ...###############..........
10 ....B############...........
11 ..S..###########............
12 ......#########.............
13 .......#######..............
14 ........#####.S.......S.....
15 B........###................
16 ..........#SB...............
17 ................S..........B
18 ....S.......................
19 ............................
20 ............S......S........
21 ............................
22 .......................B....

์‹ค์ œ ๋ฌธ์ œ์˜ ์ž…๋ ฅ์€ ์œ„์˜ ์˜ˆ์‹œ ์ž…๋ ฅ๋ณด๋‹ค ์ƒ๋‹นํžˆ ๋งŽ์œผ๋ฏ€๋กœ ์œ„์˜ ์ž…๋ ฅ์œผ๋กœ ๋ฏธ๋ฆฌ ๋‹จ์œ„ ํ…Œ์ŠคํŠธ๋ฅผ ํ•œ ํ›„ ๋‹ต์„ ์ œ์ถœํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

1 Like

์ด๋Ÿฐ x, y์ขŒํ‘œ๋กœ ๊ตฌ์„ฑ๋œ ์ •๋ณด๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ํ›ˆ๋ จ์€ ๊ฐœ๋ฐœ์ž๊ฐ€ ์ผ๋ฐ˜์ ์œผ๋กœ ๋งˆ์ฃผํ•˜๋Š” ๋ฌธ์ œ๋ฅผ ์–ด๋–ป๊ฒŒ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š”์ง€, ํ›ˆ๋ จํ•  ์ˆ˜ ์žˆ๋Š” ๋ณธ์งˆ์  ๋ฌธ์ œํ•ด๊ฒฐ ์‚ฌ๊ณ ํ›ˆ๋ จ์ด ๋  ์ˆ˜ ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

LINQ๋กœ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๊ฒƒ์€ ๋กœ์ง์˜ ๊ด€์  ๋ณด๋‹ค๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์–ด๋–ป๊ฒŒ ๋ฐ”๋ผ๋ณผ ๊ฒƒ์ด๋ƒ ์–ด๋–ป๊ฒŒ ๋ณ€๊ฒฝํ•  ๊ฒƒ์ด๋ƒ์˜ ๊ด€์ ์œผ๋กœ๋งŒ ์ ‘๊ทผํ•˜๋Š”๊ฒŒ ์ข‹์•˜์Šต๋‹ˆ๋‹ค. ๋กœ์ง์„ LINQ๋กœ ๋„ˆ๋ฌด ํ’€๋ ค๊ณ  ํ•˜๋ฉด ๋˜๋ ค ๊ฐ€๋…์„ฑ์ด ๋–จ์–ด์ง€๋Š” ๊ฒฐ๊ณผ๋ฌผ์„ ์–ป๊ฒŒ ๋˜๋”๋ผ๊ณ ์š”.

์ฒ˜๋ฆฌํ•ด์•ผ ํ•˜๋Š” ๋ฐ์ดํ„ฐ => ์ฒ˜๋ฆฌํ•œ ๋ฐ์ดํ„ฐ ๋กœ LINQ๋ฅผ ๋ฐ”๋ผ๋ณด๋ฉด์„œ ๋‹ค์–‘ํ•œ ๊ธฐ๋Šฅ์„ ์Šต๋“ํ•˜๋Š” ๊ฒƒ์ด ์ข‹์•˜์Šต๋‹ˆ๋‹ค.

์œ ์‚ฌํ•œ ๋ฌธ์ œ๋ฅผ ๋‘๋‹จ๊ณ„๋กœ ์ „๊ฐœํ•œ ๊ฒƒ์€ AoC์˜ ์ข‹์€ ์ ‘๊ทผ ๋ฐฉ๋ฒ•์ธ ๊ฒƒ ๊ฐ™์Šต๋‹ˆ๋‹ค. ์ตœ์ดˆ ๊ตฌ์„ฑํ•œ ๋กœ์ง์ด ์‹ฌํ™” ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ ์ ์ ˆํ•˜์ง€ ์•Š์•˜๋˜ ๊ฒฝํ—˜์„ ํ•˜๋Š”๋ฐ, ์ฝ”๋“œ๋Š” ์–ด๋Š ์ •๋„์˜ ํ™•์žฅ ๊ฐ€๋Šฅ์„ฑ์„ ๋‚ดํฌํ•ด์•ผ ํ•˜๋ฏ€๋กœ AoC๋ฌธ์ œ๋ฅผ ๋ฐ˜๋ณตํ•˜๋‹ค ๋ณด๋ฉด ์ข€ ๋” ์œ ์—ฐํ•œ ์ฝ”๋“œ ์ž‘์„ฑ์ด ๊ฐ€๋Šฅํ•ด์ง‘๋‹ˆ๋‹ค.

2 Likes

์ผ๋ฐ˜ ๋ฌธ์ œ๋Š” ์ฒ˜์Œ์—๋Š” ๊ฐ„๋‹จํ•˜๊ฒŒ ์ ‘๊ทผํ–ˆ์Šต๋‹ˆ๋‹ค. ์„ผ์„œ์—์„œ ๊ทผ์ ‘ ๋น„์ฝ˜๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ ๋งŒํผ '#'์„ ์ฑ„์šด ํ›„ y๊ฐ€ 10์ธ ์œ„์น˜์—์„œ '#'์˜ ๊ฐฏ์ˆ˜๋ฅผ ์„ธ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ์œ„ํ•œ ์ƒ๊ธฐ ์˜ˆ์‹œ ์ˆ˜์ค€์€ ์ถฉ๋ถ„ํžˆ ์ด ๋ฐฉ๋ฒ•์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

ํ•˜์ง€๋งŒ ์‹ค์ œ ๋ฌธ์ œ๋Š” ์ƒ๋‹นํžˆ ํฐ ๋งต(X: 61030 ~ 3971601, Y: 5535 ~ 3999227)์ด๋ฏ€๋กœ ์ตœ์‹  CPU๋กœ๋„ ์†๋„๊ฐ€ ๋Š๋ ค๋‹ต์„ ์ฐพ์ง€ ๋ชปํ•ฉ๋‹ˆ๋‹ค. ๊ด€๋ จ ์ฝ”๋“œ๋Š” Mark() ๋ฉ”์†Œ๋“œ ์ž…๋‹ˆ๋‹ค.

ํƒ์ƒ‰ํ•ด์•ผ ํ•  y์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์กŒ์œผ๋ฏ€๋กœ ์ตœ์†Œ x ~ ์ตœ๋Œ€ x ๋งŒํผ๋งŒ ์Šค์บ” ํ•˜๋Š” ๊ฒƒ์ด ํšจ์œจ์ ์ž…๋‹ˆ๋‹ค. ๊ด€๋ จ ์ฝ”๋“œ๋Š” FastCheck() ๋ฉ”์†Œ๋“œ ์ž…๋‹ˆ๋‹ค.

์‹ฌํ™”๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
์ด์ œ๋Š” ์„ผ์„œ์—์„œ ๊ฐ์ง€ํ•˜์ง€ ๋ชปํ•œ ๋น„์ฝ˜์„ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•œ ์˜ˆ์‹œ ์ž…๋ ฅ์œผ๋กœ ๊ทธ ์œ„์น˜๋ฅผ ์‚ดํŽด๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

image

์—ฌ๊ธฐ์„œ๋Š” ์ขŒํ‘œ (14, 11)์ด ๋ฉ๋‹ˆ๋‹ค.

1 Like

์‹ฌํ™” ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ ๋ฒ”์œ„๊ฐ€ (0, 0) ~ (4000000, 4000000)์ด๋ฏ€๋กœ ๋‹จ์ˆœํ•˜๊ฒŒ ๊ณ„์‚ฐํ•˜๋ฉด 4000000 * 4000000 = 16000000000000 ํšŒ์˜ ๋ฐ˜๋ณต ์—ฐ์‚ฐ์ด ํ•„์š”ํ•˜๋ฏ€๋กœ ์ƒ๋‹นํ•œ ๊ณ„์‚ฐ์ด ๋ฉ๋‹ˆ๋‹ค. ๊ทธ๋Ÿฌ๋ฏ€๋กœ ์ผ๋ฐ˜์ ์œผ๋กœ ํ’€ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

1 Like

์‹ฌํ™” ๋ฌธ์ œ๋„ ํ’€์—ˆ์Šต๋‹ˆ๋‹ค. ์—ฌ์ „ํžˆ ์†๋„๋Š” ๋Š๋ฆฌ์ง€๋งŒ ๊ฐ๋‹นํ•  ์ˆ˜์ค€์ž…๋‹ˆ๋‹ค.

์ „์ฒด ์„ผ์„œ์˜ ๊ฐ์ง€ ๊ฑฐ๋ฆฌ +1 ์˜ ์˜์—ญ์„ ๊ตฌํ•œ ํ›„

###
#v#
###

์ƒํ•˜์ขŒ์šฐ๊ฐ€ ๋ง‰ํžŒ ํ›„๋ณด๋ฅผ ๊ตฌํ•œ ํ›„, ์„ผ์„œ๊ฐ€ ๊ฐ์ง€ํ•œ ๊ฑฐ๋ฆฌ ๋ณด๋‹ค ํฐ ๊ฒƒ๋งŒ ์ทจํ•œ ํ›„, (0, 0) ~ (4000000, 4000000) ๋ฒ”์œ„ ์•ˆ์— ์žˆ๋Š” ์ขŒํ‘œ๋ฅผ ๊ตฌํ–ˆ์Šต๋‹ˆ๋‹ค.

var outsidePoints = points
    .Select(x => GetOutsides(x.Sensor, x.Sensor.Distance(x.Beacon)).ToArray())
    .SelectMany(x => x)
    .GroupBy(x => x).Where(g => g.Count() >= 4).Select(x => x.Key)
    .ToArray()
    .Where(x => points.All(y => y.Sensor.Distance(x) > y.Sensor.Distance(y.Beacon) is true))
    .Where(x => x.X is >= 0 and <= 4000000 && x.Y is >= 0 and <= 4000000)
    .First();
1 Like

๋‹ค๋ฅธ ๋ถ„๋“ค์˜ ํ’€์ด๊ฐ€ ๋‹ค ๋‹ค๋ฅด๋‹ค๋Š” ์ ์€ ํฅ๋ฏธ๋กญ์Šต๋‹ˆ๋‹คโ€ฆ

๋ฌธ์ œ์˜ ๋‚œ์ด๋„๊ฐ€ ๋” ์–ด๋ ค์›Œ์กŒ์Šต๋‹ˆ๋‹ค. ํ•˜๋ฃจ์— ํ•œ ๋ฌธ์ œ ํ’€๊ธฐ๋„ ์กฐ๊ธˆ ๋ฒ…์ฐจ์ง€๋Š”๊ตฐ์š”.

1 Like

image

1๋ฒˆ ๋ฌธ์ œ๋ฅผ ์ฐธ์—ฌํ•œ ๋ถ„์ด ๋Œ€๋žต 24๋งŒ๋ช…์ด๋ฏ€๋กœ ์ง€๊ธˆ์˜ ์ €์˜ ์Šค์ฝ”์–ด๋Š” 24๋งŒ๋ช… ์ค‘ 3.6๋งŒ๋ช…์— ์œ„์น˜ํ•ด ์žˆ์Šต๋‹ˆ๋‹ค. ์•„์ง 10๋ฌธ์ œ๊ฐ€ ๋‚จ์•˜์œผ๋ฏ€๋กœ ๊ฐˆ ๊ธธ์ด ๋ฉ€๊ตฐ์š”โ€ฆ

1 Like

Day 16

์ผ๋ฐ˜

ํŠน์ •ํ•œ ๊ฒฝ๋กœ๋ฅผ ๊ฐ€์ง„ ๋ฐธ๋ธŒ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ์—ด์–ด์„œ 30๋ถ„ ๋™์•ˆ ๊ฐ€ํ•˜๋Š” ์••๋ ฅ์˜ ํ•ฉ์„ ๊ฐ€์žฅ ํฌ๊ฒŒ ๋งŒ๋“œ๋Š” ๊ฒƒ์ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋‹ค์Œ์˜ ์ž…๋ ฅ์€

Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
Valve BB has flow rate=13; tunnels lead to valves CC, AA
Valve CC has flow rate=2; tunnels lead to valves DD, BB
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
Valve EE has flow rate=3; tunnels lead to valves FF, DD
Valve FF has flow rate=0; tunnels lead to valves EE, GG
Valve GG has flow rate=0; tunnels lead to valves FF, HH
Valve HH has flow rate=22; tunnel leads to valve GG
Valve II has flow rate=0; tunnels lead to valves AA, JJ
Valve JJ has flow rate=21; tunnel leads to valve II

๋‹ค์Œ ์ฒ˜๋Ÿผ ์‹œ๊ฐํ™” ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์‹œ๊ฐํ™”๋Š” ๋ฌธ์ œ๋ฅผ ์ดํ•ดํ•˜๋Š”๋ฐ ํฐ ๋„์›€์ด ๋˜๋ฏ€๋กœ ์ผ์ƒ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ๋„ ์ ์šฉํ•ด๋ด„ ์งํ•ฉ๋‹ˆ๋‹ค.

image

์ด๋™ํ•˜๋Š”๋ฐ 1๋ถ„์ด ์†Œ์š”๋˜๊ณ  ๋ฐธ๋ธŒ๋ฅผ ์—ฌ๋Š”๋ฐ 1๋ถ„์ด ์†Œ์š”๋ฉ๋‹ˆ๋‹ค. ์ด๊ฒƒ์„ ๊ณ ๋ คํ•ด์„œ 30๋ถ„๋™์•ˆ์˜ ์••๋ ฅ์˜ ํ•ฉ์„ ์ตœ๋Œ€์น˜๋กœ ๋งŒ๋“ค์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

1 Like

๋ฌธ์ œ๋Š” ํ‘ธ๋Š” ์ „๊ฐœ๋Š”โ€ฆ

์ž…๋ ฅ์„ ๊ทธ๋ž˜ํ”„ ํ˜•ํƒœ๋กœ ๋ณ€ํ™˜ํ•˜๊ณ ,
์ ์ ˆํ•œ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•ด์„œ ์ตœ์ ์˜ ์ด๋™ ๊ฒฝ๋กœ๋ฅผ ๊ฒฐ์ •ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

(์ผ๋ฐ˜ ๋ฌธ์ œ์—์„œ ์‚ฌ๋žŒ๊ณผ ์ฝ”๋ผ๋ฆฌ๊ฐ€ ๋‚˜์˜ค๋ฏ€๋กœ ์‹ฌํ™” ๋ฌธ์ œ๋Š” ์ด๋™ํ•ด์•ผ ํ•˜๋Š” ๋Œ€์ƒ์ด ๋‘˜์ผ ๊ฒƒ ๊ฐ™๊ตฐ์š”!)

2 Likes

ํ•˜๋ฃจ ๋ฌธ์ œ๊ฐ€ ์ด์ œ๋Š” 2์‹œ๊ฐ„์ด ๋„˜๊ฒŒ ์†Œ์š”๋˜๋ฏ€๋กœโ€ฆ ์ž ์‹œ ํ™€๋”ฉํ•˜๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ๋ฐ”์œ ๊ฒƒ์ด ๋๋‚˜๋ฉด ๋‹ค์‹œ ์‹œ์ž‘ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค.

3 Likes