Рыцарь на Кольце мрачен

48

Введение

Арон Нимзович был ведущим шахматным мастером и влиятельным шахматным писателем.

В его книге «Моя система» первая глава рассказывает о важности центра и о том, почему вы должны доминировать в нем. Простая причина в том, что ваши фигуры имеют больше возможных прямых следующих ходов, когда находятся в центре, что снова дает игроку больше силы.

Это становится очень ясным, если взглянуть на различные позиции коня и его возможные последующие ходы (показаны розовым цветом) на пустой доске:

введите описание изображения здесь

Задача

Оцените количество возможных прямых следующих ходов коня на пустой доске в зависимости от его положения.

Входные характеристики

Положение рыцаря.

Сначала х (столбец), а затем у (строка). 0 0это левый нижний угол.

Для простоты я изменил метки шахматной доски только на цифры. В наших примерах и тестовых примерах мы используем индекс на основе 0, однако вы можете использовать индекс на основе 1.

Вы можете использовать любой тип возможных форматов ввода, массив, аргументы функций и т. Д.

Выходные характеристики

Количество потенциальных прямых следующих ходов для коня на пустой доске.

Тестовые случаи

3 4 => 8
4 6 => 6
7 7 => 2
1 0 => 3

В тестовых примерах используется индекс на основе 0. Полная сетка значений:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
code-golf math chess starcorder
источник
9
Хороший первый вызов! :-)
Луис Мендо
14
«Рыцарь на краю мрачен»
2
@stacey Ваш комментарий был бы отличным названием для этой загадки :)
starcorder
6
Теперь по действительно сложному вопросу: все ли красные рыцари на изображении выше имеют одинаковый цвет?
mbomb007

Ответы:

25

Python 2 , 35 байт

lambda x,y:50/(8+x*x/7-x+y*y/7-y)-4

Попробуйте онлайн!

Python 2 , 39 байт

lambda x,y:50/(8-x*(7-x)/5-y*(7-y)/5)-4

Попробуйте онлайн!

Принимает входы с 0 индексами.

Выражение x*(7-x)/5принимает значения координат 0..7в

[0, 1, 2, 2, 2, 2, 1, 0]

( min(x,7-x,2)делает то же самое, но длиннее.) Суммируя это xи yполучая правильный шаблон, но с неправильными числами

0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

(См . Решение Нейла для лучшего рассуждения о том, почему это дает правильную схему.)

Наконец, отображение a -> 50/(8-a)-4с разделением по полу дает правильные значения

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Альтернативное решение одинаковой длины с 1-индексированными входами:

lambda x,y:(x*(9-x)/6+y*(9-y)/6)**2/6+2
XNOR
источник
(7-a)*a/5на 3 байта короче min(a,7-a,2).
Нил
1
*lна самом деле стоит всего один байт, lambda a,b:"23468"[(7-a)*a/5+(7-b)*b/5]всего 41 байт.
Нил
@Neil Я только что нашел то же самое, с x*(9-x)/6одним индексом.
xnor
1
Почему бы вам не использовать, <strike>как все, чтобы показать прогресс в гольф?
Безумный
4
@ Insane Я думаю, это выглядит ужасно и на самом деле не помогает. Код - это важная вещь, и любой, кто хочет увидеть его развитие, все равно должен заглянуть в историю редактирования. Когда мой старый код достаточно отличается, чтобы его можно было показать, я показываю версии, как здесь . Но в этом вопросе все незначительные улучшения в одной и той же стратегии, поэтому я счел это более понятным, просто упомянув о различных возможностях.
xnor
17

MATL , 17 14 13 12 байт

Спасибо @Neil за 1 байт!

8:HZ^ZP5X^=s

Вход основан на 1.

Попробуйте онлайн!

объяснение

Это вычисляет евклидово расстояние от входа до каждой из 64 позиций на шахматной доске и определяет, сколько из этих значений равно квадратному корню из 5.

Поскольку координаты являются целочисленными значениями, мы можем быть уверены, что два значения с плавающей запятой, представляющие квадратный корень из 5 (рассчитанный по координатам и вычисленный напрямую), действительно одинаковы.

8:      % Push array [1 2 ... 8]
H       % Push 2
Z^      % Cartesian power. Gives 2D array [1 1; 1 2; ... 1 8; 2 1; ... 8 8]     
ZP      % Implicit input. Compute Euclidean distances, considering each row as a point
5X^     % Square root of 5
=s      % Compute how many squared distances equal sqrt(5). Implicit display
Луис Мендо
источник
1
Впечатляет и спасибо за объяснение
starcorder
1
Если сравнение квадрата корня квадратного из 5 до 5 не удается из-за ошибок округления, разве вы не можете хотя бы сравнить корень квадратный из 5 с квадратным корнем из 5?
Нил
@Neil Спасибо за идею! Да, поскольку вычисления выполняются с целыми числами, я могу быть уверен, что два «корня из 5» - это одно и то же doubleчисло. Муравей спасает байт
Луис Мендо
15

Mathematica 63 43 байта

С 20 байтами сохранено благодаря предложениям Мартина Эндера!

EdgeCount[8~KnightTourGraph~8,#+1+8#2/<->_]&

Выше указано количество квадратов, которые находятся на расстоянии 1 шага от данной ячейки на полном графике тура рыцарей.

g=KnightTourGraph[8,8,VertexLabels->"Name",Axes->True]

отображает полный круговой график коня с именами вершин и координатами. Обратите внимание, что по умолчанию в Mathematica используется индексация координат по одному.

график

#+1+8#2&[r,f]Converts возвращает вершину, соответствующую квадрату в ранге (строке) rи файле (столбце) f, используя нулевые значения в качестве входных данных.

Например #+1+8#2&[2,1]возвращает 11.

EdgeCount дает число ребер в графе окрестностей.

Края для ранга 2, файл 1 (квадрат 11):

IncidenceList[8~KnightTourGraph~8, 8 #2 + # + 1] &[2, 1]

(*{1 <-> 11, 5 <-> 11, 11 <-> 17, 11 <-> 21, 11 <-> 26, 11 <-> 28}*)

Подсвеченные края:

HighlightGraph[g, {1, 5, 11, 17, 21, 26, 28, Style[1 <-> 11, Thick, Blue], Style[5 <-> 11, Thick, Blue], Style[11 <-> 17, Thick, Blue], Style[11 <-> 21, Thick, Blue], Style[11 <-> 26, Thick, Blue], Style[11 <-> 28, Thick, Blue]},GraphHighlightStyle -> "DehighlightFade", PlotRangePadding -> .5]

основной момент

Метод 2: Евклидово расстояние

70 байт

Этот метод более длинный, но, возможно, представляет некоторый интерес. Подход заключается в проверке евклидова расстояния между центром шахматной доски и ячейкой интереса.

Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&

Иллюстрация

Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{0, 0}
Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{3, 3}

2

8

Чтобы помочь визуализировать, как расстояние от центра шахматной доски достаточно для присвоения значения.

values={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};
f[x_]:=Text[x,#]&/@Position[values,x]r_~w~p_:=RegionMember[{3.5`,3.5`}~Disk~r,p]
h@y_:=Which[2.2~w~y,8,3~w~y,6,4~w~y,4,4.6~w~y,3,2<3,2]

Graphics[{Circle[{4.5, 4.5}, 2.3], Circle[{4.5, 4.5}, 3],

Круг [{4.5, 4.5}, 4],

Circle [{4.5, 4.5}, 4.6], Flatten [f / @ {2, 3, 4, 6, 8}, 1]}, Axes -> True, AxesOrigin -> {-1, -1}]

Числа 2.2, 3, 4 и 4.6 являются радиусами окружностей.

образ

DavidC
источник
1
Отличный гастрольный график
starcorder
20
KnightTourGraphMathematica и его встроенные элементы ... :-)
Луис Мендо
Я думаю, что #в конце вашего исходного кода есть паразит (прямо перед ]). Вы должны быть в состоянии использовать IncidenceListвместо, EdgeList@NeighborhoodGraphхотя. (В качестве альтернативы, есть также EdgeCount, но я думаю, что в конечном итоге будет дольше.)
Мартин Эндер
1
Ой, подождите, это на самом деле короче:EdgeCount[8~KnightTourGraph~8,#+1+8#2<->_]&
Мартин Эндер
EdgeCountэто очень круто!
DavidC
12

JavaScript (ES6), 38 байт

(x,y)=>+"23468"[((7-x)*x+(7-y)*y)/5|0]

Принимает 0-индексированные входы. Пояснение: посмотрите на квадраты расстояний до центра:

24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5

Количество доступных квадратов делится на пять полос:

8    0-5
6    5-10
4   10-15
3   15-20
2   20-25

На самом деле я вычисляю 24,5 - (3,5 - х) ** 2 - (3,5 - у) ** 2 = (7 - х) * х + (7 - у) * у, поскольку это более короткий расчет, но все, что он делает, это наоборот порядок полос.

Нил
источник
Супер лаконичный и очень хороший подход, так что мне больше не нужно запускать собственное JS-решение :)
starcorder
Хороший вопрос о том, что формула эквивалентна квадрату радиуса. Я думал, x*(7-x)что это просто операция, которая выглядит как нисходящая дуга 0..7и случается с подгонкой кривой, но это объясняет, почему она дает такой хороший шаблон при суммировании для xи y.
xnor
11

Желе, 10 байт

8ṗ2_³²S€ċ5

1-индексироваться. Принимает единственный аргумент формы [x,y]. Попробуй это здесь.

8ṗ2          Cartesian square [[1,1],[1,2]…[8,8]]
   _³        Subtract the input
     ²S€     Compute the norm of each vector
        ċ5   Count fives

Денис спас байт!

Линн
источник
Всего одиннадцать байтов, вау!
звездная запись
Я видел этот вопрос утром, и это именно тот алгоритм, который, как я думал, я бы реализовал в Jelly, когда у меня было время. : P
PurkkaKoodari
8

Mathematica, 44 40 байт

В настоящее время у меня есть три решения с одинаковым количеством байтов:

2[3,4,6,8][[Tr@⌊3.2-.8Abs[#-4.5]⌋]]&
Tr@⌈.85(4-Abs[#-4.5])⌉/.{5->6,6->8}&
⌊Tr@⌈.85(4-Abs[#-4.5])⌉^1.1608⌋&

Все это безымянные функции, которые принимают пару координат типа {3, 4}, которые основаны на 1.

Я попытался придумать несколько явную формулу. Общий шаблон на всей доске выглядит так:

введите описание изображения здесь

Фактические значения этих цветов (от самых светлых до самых темных) 2, 3, 4, 6, 8. Это:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

Сначала мы используем симметрию, сдвигая начало координат к центру, беря абсолютное значение и вычитая результат из 4. Это дает нам координаты 0.5для 3.5увеличения от каждого угла. Чтобы сделать координаты центра одинаковыми, нам нужно сопоставить 0.5и 1.5разные значения, 2.5и 3.5одно и то же значение. Это легко сделать, умножив на 0.8(дает {0.4, 1.2, 2., 2.8}) и получив результат. Так что теперь у нас есть {0, 1, 2, 2}как расстояния от центра. Если мы сложим координаты в каждой ячейке, мы получим эту таблицу:

0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

Это имеет уникальные значения для всех возможных результатов, поэтому мы просто используем его как индекс в 2[3,4,6,8].

Во втором варианте мы используем потолок вместо пола. Таким образом, 2, 3и 4уже правильно, но мы получаем 5и 6вместо 6и 8, таким образом , мы исправим их вручную с помощью правила подстановки.

Наконец, в третьем варианте, мы расширим 5и 6вверх 6и 8с помощью потенцирования, а затем другой операции пола.

Мартин Эндер
источник
Мне очень нравится подход с использованием общей схемы платы, отлично!
Звездная запись
6

APL, 21 символ

{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}

По-английски:

  • (⍳8 8): Массив 8x8 ранг-2, содержащий координаты всех ячеек;
  • +/¨×⍨(⍳8 8)-⊂⍵: квадрат евклидовых расстояний данной ячейки относительно каждой ячейки на доске;
  • 5=: матрица 0/1, где 1 появляются на квадрате расстояний, равных 5;
  • +/,: суммировать сплюснутую матрицу

Тест (в источнике 1):

    f←{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}
    f¨1+(3 4)(4 6)(7 7)(1 0)
8 6 2 3

В этой форме: 

f←{+/,5=+/¨×⍨(⍳⍺)-⊂⍵}

левый аргумент может указывать размеры доски. Следовательно, 8 8 fбудет работать на стандартной квадратной шахматной доске. Но на большой прямоугольной доске тестовые случаи дали бы другие результаты. Например, на доске 12x10:

    g←(10 12)∘f
    g¨1+(3 4)(4 6)(7 7)(1 0)
8 8 8 3
lstefano
источник
В жаргоне APL матрица - это массив ранга 2, ничего не сказано о содержимом ячеек. Годы (ab) использования терминов сделали меня нечувствительным к этому. Я обновлю описание для более традиционно склонных читателей. Спасибо.
Истефано
@Istefano То, что использование «ранга» как «числа измерений», похоже, страдает от того же недуга :-P
Луис Мендо
Я буду ... Вы правы! Вы можете видеть, что прошло много времени с тех пор, как я взял линейную алгебру. Я сдаюсь :-)
lstefano
1
Полная программа, 27: ≢⍸5=+/¨×⍨-∘⎕¨⍳8 8 Попробуйте онлайн!
Адам
@ Adám ты имеешь в виду 17
нг
6

Java - 160 150 байт

int m(int r,int c){int m=0,i,j;for(i=0;i<3;i+=2)for(j=0;j<3;j+=2){m+=r+i>0&r+i<9&c+2*j>1&c+2*j<11?1:0;m+=r+2*i>1&r+2*i<11&c+j>0&c+j<9?1:0;}return m;}

Ungolfed:

public static int m(int r, int c) {
    int m=0;
    for(int i=-1;i<2;i+=2)
        for(int j=-1;j<2;j+=2){
            m += r+i>-1 && r+i<8 && c+2*j>0 && c+2*j<8 ? 1:0;
            m += r+2*i>0 && r+2*i<8 && c+j>1 && c+j<8 ? 1:0;
        }
    return m;
}

Код ungolfed идентичен, за исключением изменения границ цикла for для сохранения 4 байтов. Работает, повторяя каждое возможное движение и выполняя проверку границ (> 0 и <8). Использует тот факт, что смещения (1, 2), (2, 1), (-1, 2), (-2, 1) и т. Д., И может проверить 2 хода для каждого значения i и j.

Изменить: 10 байтов сохранено благодаря предложениям Лики Нун и u902383.

ejaszewski
источник
Это было также быстро, приятно!
Звездная запись
Там была ошибка, она была исправлена.
ejaszewski
1
int m=0,i=-1,j;чтобы сохранить некоторые байты
Leaky Nun
1
измените логическое И на побитовое И, и это позволит вам удалить дополнительные 6 символов
user902383
6

C, 44 байта

f(x,y){return "23468"[((7-x)*x+(7-y)*y)/5];}

Но это лучше

f(x,y){return "2344443234666643468888644688886446888864468888643466664323444432"[x*8+y];}
Джакомо Гарабелло
источник
1
Отсутствует ;. Не скомпилируется.
Угорен
@GiacomoGarabello См .: meta.codegolf.stackexchange.com/a/1146/55729
Джекджек,
1
Это не фрагмент, это функция, и это не запрещено пост функций. Извините за пропущенную точку с запятой. Исправлена.
Джакомо Гарабелло
5

Haskell, 49 48 байтов

w=[0..7]
x%y=sum[1|a<-w,b<-w,(a-x)^2+(b-y)^2==5]
Damien
источник
1
Вы можете сохранить [0..7]в переменную 1 байт.
xnor
5

Java, 81 символ (113 байт)

int r(int a,int b){return "⍄䐲㑦晃䚈衤䚈衤䚈衤䚈衤㑦晃⍄䐲".codePointAt(a*2+b/4)>>(3-b%4)*4&15;}

Закодируйте всю таблицу результатов как таблицу Юникода, а затем получите соответствующие байты, выполняя побитовые операции.

Вы можете увидеть это онлайн здесь: https://ideone.com/K9BojC

cliffroot
источник
3

Python, 94 байта

lambda x,y,a=[2,1,-1,-2,-2,-1,1,2]:list((9>x+a[i]>0)&(9>y+a[5-i]>0)for i in range(8)).count(1)

Использует 1 на основе индексации.

Демо на https://repl.it/C6gV .

Чак Моррис
источник
2

Pyth - 33 15 байт

Спасибо @LeakyNun за уменьшение моего размера вдвое.

Перестановка карт и V, возможно, позволит немного поиграть в гольф.

/sM*Fm^R2-Rd8Q5

Тестовый пакет .

Maltysen
источник
1
Это было быстро, приятно!
Звездная запись
2
15 байтов
прохудившаяся монахиня
1

На самом деле, 18 байт

`;7-2km`MΣ8-:50\¬¬

Попробуйте онлайн!

Это реализует ту же формулу , что и многие другие ответы были с помощью: 50/(8-x*(7-x)//5+y*(7-y))//5)-4. Ввод принимается в виде списка: [x,y](или любой итеративный литерал в Python, например (x,y)или x,y).

Объяснение:

`;7-2km`MΣ8-:50\¬¬
`;7-2km`M           for each value in input:
 ;7-                  make a copy, subtract from 7
    2                 push 2
     km               minimum of the three values (x, 7-x, 2)
         Σ          sum
          8-        subtract from 8
            :50\    integer divide 50 by the value
                ¬¬  subtract 2 twice
Мего
источник