3 ms·
Why did they only solve for 7 Queens and not 8 Queens? I'm reminded of https://github.com/type-challenges/type-challenges https://github.com/type-challenges/ty
by Buttons840 4y ago
Why did they only solve for 7 Queens and not 8 Queens?
I'm reminded of https://github.com/type-challenges/type-challenges https://github.com/type-challenges/type-challenges -- I've only looked at some of the more challenging problems, but one involves writing a JSON parser in the type system. The easy problems look reasonably useful to solve.
- ycitm 4y agoI wondered if anyone would spot this :) There's a recursion depth limit of 500 on the TypeScript compiler, which prevents this solution working for N > 7 Even Aphyr's original Haskell solution only demonstrates N = 6, so in some sense this is an improvement on the state of the art for type-level N Queens solutions /s
- davidmurdoch 4y agoI don't really know what it means, but I've seen it used to work around depth issues in Typescript, but can this use a "trampoline"?
- ycitm 4y agoI don't think there's any way to do iteration in the type system (other than recursion), so there's no way around it. I considered forking the compiler to set a deeper limit, but at some point Typescript itself is going to stack overflow. Also that probably goes a bit beyond what Criss is expecting in an interview...
- planede 4y agoI don't know about the typescript compiler, but the way around template recursion limits in "classic" C++ template metaprogramming is to figure out a way to make it O(log N) depth instead of O(N) (for some value of N). Like instead of linearly iterating through a range of types through recursion, you divide and conquer. Easier said than done, but possible in some cases.