Jane Triads

// https://www.janestreet.com/puzzles/triads/

package main

import (
	"context"
	"fmt"
	"strings"
	"time"
)

//  ▲
// ▲ ▲
const (
	ci = "●"
	tu = "▲"
	td = "▼"
)

type point struct {
	pos   int
	group int // -1 0 1 down, none, up
}

func (p point) String() string {
	switch p.group {
	case 1:
		return tu
	case -1:
		return td
	default:
		return ci
	}
}

type value struct {
	row, col, group int
}

func next(ctx context.Context, grid [][]point, row, col int, seen map[value]bool) bool {
	if ctx.Err() != nil {
		return false // break
	}

	col += 1
	if col > row {
		col = 0
		row += 1
		if row == len(grid) {
			return true // solved!
		}
	}
	return solve(ctx, grid, row, col, seen)
}

func solve(ctx context.Context, grid [][]point, row, col int, seen map[value]bool) bool {
	p := &grid[row][col]
	if p.group != 0 {
		return next(ctx, grid, row, col, seen)
	}

	// up arrow
	//   .
	//  / \
	// . - .
	if rowNext := row + 1; rowNext != len(grid) && !seen[value{row, col, 1}] {
		p1 := &grid[rowNext][col]
		p2 := &grid[rowNext][col+1]

		if p1.group == 0 && p2.group == 0 {
			p.group = 1
			p1.group = 1
			p2.group = 1
			if ans := next(ctx, grid, row, col, seen); ans {
				return ans
			}
			p.group = 0
			p1.group = 0
			p2.group = 0

			//seen[value{row, col, 1}] = true
		}
	}

	// down arrow
	// . - .
	//  \ /
	//   .
	if rowNext, colNext := row+1, col+1; rowNext != len(grid) && colNext != len(grid[row]) && !seen[value{row, col, -1}] {
		p1 := &grid[row][colNext]
		p2 := &grid[rowNext][colNext]

		if p1.group == 0 && p2.group == 0 {
			p.group = -1
			p1.group = -1
			p2.group = -1
			if ans := next(ctx, grid, row, col, seen); ans {
				return ans
			}
			p.group = 0
			p1.group = 0
			p2.group = 0

			//seen[value{row, col, -1}] = true
		}
	}

	return false // nope
}

func main() {
	ctx := context.Background()

	for n := 2; n < 40; n++ {
		start := time.Now()
		ctx, cancel := context.WithTimeout(ctx, time.Second*5)

		var count int

		var grid [][]point
		for i := 0; i < n; i++ {
			x := make([]point, i+1)
			for j := range x {
				x[j] = point{pos: count + j + 1}
			}
			count += i + 1 // N + ... + 3 + 2 + 1
			grid = append(grid, x)
		}

		seen := make(map[value]bool)

		ans := solve(ctx, grid, 0, 0, seen)
		elapsed := time.Now().Sub(start)
		if !ans {
			if err := ctx.Err(); err != nil {
				fmt.Printf("Timeout N=%d in %s.\n", n, elapsed)
			} else {
				fmt.Printf("Nope N=%d in %s.\n", n, elapsed)
			}
		} else {
			fmt.Printf("Solved N=%d in %s!\n", n, elapsed)

			for i, xs := range grid {
				ss := make([]string, len(xs))
				for j, p := range xs {
					ss[j] = p.String()
				}
				fmt.Printf("%d\t%s%s\n", i+1, strings.Repeat(" ", n-i), strings.Join(ss, " "))
			}
		}
		cancel()
	}
}