281. Java 5, 11628 bajtów, A000947
// package oeis_challenge;
import java.util.*;
import java.lang.*;
class Main {
// static void assert(boolean cond) {
// if (!cond)
// throw new Error("Assertion failed!");
// }
/* Use the formula a(n) = A000063(n + 2) - A000936(n).
It's unfair that I use the formula of "number of free polyenoid with n
nodes and symmetry point group C_{2v}" (formula listed in A000063)
without understanding why it's true...
*/
static int catalan(int x) {
int ans = 1;
for (int i = 1; i <= x; ++i)
ans = ans * (2*x+1-i) / i;
return ans / -~x;
}
static int A63(int n) {
int ans = catalan(n/2 - 1);
if (n%4 == 0) ans -= catalan(n/4 - 1);
if (n%6 == 0) ans -= catalan(n/6 - 1);
return ans;
}
static class Point implements Comparable<Point> {
final int x, y;
Point(int _x, int _y) {
x = _x; y = _y;
}
/// @return true if this is a point, false otherwise (this is a vector)
public boolean isPoint() {
return (x + y) % 3 != 0;
}
/// Translate this point by a vector.
public Point add(Point p) {
assert(this.isPoint() && ! p.isPoint());
return new Point(x + p.x, y + p.y);
}
/// Reflect this point along x-axis.
public Point reflectX() {
return new Point(x - y, -y);
}
/// Rotate this point 60 degrees counter-clockwise.
public Point rot60() {
return new Point(x - y, x);
}
@Override
public boolean equals(Object o) {
if (!(o instanceof Point)) return false;
Point p = (Point) o;
return x == p.x && y == p.y;
}
@Override
public int hashCode() {
return 21521 * (3491 + x) + y;
}
public String toString() {
// return String.format("(%d, %d)", x, y);
return String.format("setxy %d %d", x * 50 - y * 25, y * 40);
}
public int compareTo(Point p) {
int a = Integer.valueOf(x).compareTo(p.x);
if (a != 0) return a;
return Integer.valueOf(y).compareTo(p.y);
}
/// Helper class.
static interface Predicate {
abstract boolean test(Point p);
}
static abstract class UnaryFunction {
abstract Point apply(Point p);
}
}
static class Edge implements Comparable<Edge> {
final Point a, b; // guarantee a < b
Edge(Point x, Point y) {
assert x != y;
if (x.compareTo(y) > 0) { // y < x
a = y; b = x;
} else {
a = x; b = y;
}
}
public int compareTo(Edge e) {
int x = a.compareTo(e.a);
if (x != 0) return x;
return b.compareTo(e.b);
}
}
/// A graph consists of multiple {@code Point}s.
static class Graph {
private HashMap<Point, Point> points;
public Graph() {
points = new HashMap<Point, Point>();
}
public Graph(Graph g) {
points = new HashMap<Point, Point>(g.points);
}
public void add(Point p, Point root) {
assert(p.isPoint());
assert(root.isPoint());
assert(p == root || points.containsKey(root));
points.put(p, root);
}
public Graph map(Point.UnaryFunction fn) {
Graph result = new Graph();
for (Map.Entry<Point, Point> pq : points.entrySet()) {
Point p = pq.getKey(), q = pq.getValue();
assert(p.isPoint()) : p;
assert(q.isPoint()) : q;
p = fn.apply(p); assert(p.isPoint()) : p;
q = fn.apply(q); assert(q.isPoint()) : q;
result.points.put(p, q);
}
return result;
}
public Graph reflectX() {
return this.map(new Point.UnaryFunction() {
public Point apply(Point p) {
return p.reflectX();
}
});
}
public Graph rot60() {
return this.map(new Point.UnaryFunction() {
public Point apply(Point p) {
return p.rot60();
}
});
}
@Override
public boolean equals(Object o) {
if (o == null) return false;
if (o.getClass() != getClass()) return false;
Graph g = (Graph) o;
return points.equals(g.points);
}
@Override
public int hashCode() {
return points.hashCode();
}
Graph[] expand(Point.Predicate fn) {
List<Graph> result = new ArrayList<Graph>();
for (Point p : points.keySet()) {
int[] deltaX = new int[] { -1, 0, 1, 1, 0, -1};
int[] deltaY = new int[] { 0, 1, 1, 0, -1, -1};
for (int i = 6; i --> 0;) {
Point p1 = new Point(p.x + deltaX[i], p.y + deltaY[i]);
if (points.containsKey(p1) || !fn.test(p1)
|| !p1.isPoint()) continue;
Graph g = new Graph(this);
g.add(p1, p);
result.add(g);
}
}
return result.toArray(new Graph[0]);
}
public static Graph[] expand(Graph[] graphs, Point.Predicate fn) {
Set<Graph> result = new HashSet<Graph>();
for (Graph g0 : graphs) {
Graph[] g = g0.expand(fn);
for (Graph g1 : g) {
if (result.contains(g1)) continue;
result.add(g1);
}
}
return result.toArray(new Graph[0]);
}
private Edge[] edges() {
List<Edge> result = new ArrayList<Edge>();
for (Map.Entry<Point, Point> pq : points.entrySet()) {
Point p = pq.getKey(), q = pq.getValue();
if (p.equals(q)) continue;
result.add(new Edge(p, q));
}
return result.toArray(new Edge[0]);
}
/**
* Check if two graphs are isomorphic... under translation.
* @return {@code true} if {@code this} is isomorphic
* under translation, {@code false} otherwise.
*/
public boolean isomorphic(Graph g) {
if (points.size() != g.points.size()) return false;
Edge[] a = this.edges();
Edge[] b = g.edges();
Arrays.sort(a);
Arrays.sort(b);
// for (Edge e : b)
// System.err.println(e.a + " - " + e.b);
// System.err.println("------- >><< ");
assert (a.length > 0);
assert (a.length == b.length);
int a_bx = a[0].a.x - b[0].a.x, a_by = a[0].a.y - b[0].a.y;
for (int i = 0; i < a.length; ++i) {
if (a_bx != a[i].a.x - b[i].a.x ||
a_by != a[i].a.y - b[i].a.y) return false;
if (a_bx != a[i].b.x - b[i].b.x ||
a_by != a[i].b.y - b[i].b.y) return false;
}
return true;
}
// C_{2v}.
public boolean correctSymmetry() {
Graph[] graphs = new Graph[6];
graphs[0] = this.reflectX();
for (int i = 1; i < 6; ++i) graphs[i] = graphs[i-1].rot60();
assert(graphs[5].rot60().isomorphic(graphs[0]));
int count = 0;
for (Graph g : graphs) {
if (this.isomorphic(g)) ++count;
// if (count >= 2) {
// return false;
// }
}
// if (count > 1) System.err.format("too much: %d%n", count);
assert(count > 0);
return count == 1; // which is, basically, true
}
public void reflectSelfType2() {
Graph g = this.map(new Point.UnaryFunction() {
public Point apply(Point p) {
return new Point(p.y - p.x, p.y);
}
});
Point p = new Point(1, 1);
assert (p.equals(points.get(p)));
points.putAll(g.points);
assert (p.equals(points.get(p)));
Point q = new Point(0, 1);
assert (q.equals(points.get(q)));
points.put(p, q);
}
public void reflectSelfX() {
Graph g = this.reflectX();
points.putAll(g.points); // duplicates doesn't matter
}
}
static int A936(int n) {
// if (true) return (new int[]{0, 0, 0, 1, 1, 2, 4, 4, 12, 10, 29, 27, 88, 76, 247, 217, 722, 638, 2134, 1901, 6413})[n];
// some unreachable codes here for testing.
int ans = 0;
if (n % 2 == 0) { // reflection type 2. (through line 2x == y)
Graph[] graphs = new Graph[1];
graphs[0] = new Graph();
Point p = new Point(1, 1);
graphs[0].add(p, p);
for (int i = n / 2 - 1; i --> 0;)
graphs = Graph.expand(graphs, new Point.Predicate() {
public boolean test(Point p) {
return 2*p.x > p.y;
}
});
int count = 0;
for (Graph g : graphs) {
g.reflectSelfType2();
if (g.correctSymmetry()) {
++count;
// for (Edge e : g.edges())
// System.err.println(e.a + " - " + e.b);
// System.err.println("------*");
}
// else System.err.println("Failed");
}
assert (count%2 == 0);
// System.err.println("A936(" + n + ") count = " + count + " -> " + (count/2));
ans += count / 2;
}
// Reflection type 1. (reflectX)
Graph[] graphs = new Graph[1];
graphs[0] = new Graph();
Point p = new Point(1, 0);
graphs[0].add(p, p);
if (n % 2 == 0) graphs[0].add(new Point(2, 0), p);
for (int i = (n-1) / 2; i --> 0;)
graphs = Graph.expand(graphs, new Point.Predicate() {
public boolean test(Point p) {
return p.y > 0;
}
});
int count = 0;
for (Graph g : graphs) {
g.reflectSelfX();
if (g.correctSymmetry()) {
++count;
// for (Edge e : g.edges())
// System.err.printf(
// "pu %s pd %s\n"
// // "%s - %s%n"
// , e.a, e.b);
// System.err.println("-------/");
}
// else System.err.println("Failed");
}
if(n % 2 == 0) {
assert(count % 2 == 0);
count /= 2;
}
ans += count;
// System.err.println("A936(" + n + ") = " + ans);
return ans;
}
public static void main(String[] args) {
// Probably
if (! "1.5.0_22".equals(System.getProperty("java.version"))) {
System.err.println("Warning: Java version is not 1.5.0_22");
}
// A936(6);
for (int i = 0; i < 20; ++i)
System.out.println(i + " | " + (A63(i+9) - A936(i+7)));
//A936(i+2);
}
}
Wypróbuj online!
Dygresja:
- Testowane lokalnie w Javie 5. (takie, że ostrzeżenie nie jest drukowane - patrz karta debugowania TIO)
- Nie rób Zawsze. Posługiwać się. Jawa. 1. Jest bardziej szczegółowy niż Java.
Może to przerwać łańcuch. - Różnica (7 dni i 48 minut) to nie więcej niż przerwa utworzona przez tę odpowiedź , która wynosi 7 dni i 1 godziny i 25 minut później niż poprzednia .
Nowy rekord na dużej liczbie bajtów! Ponieważ (błędnie?) Używam spacji zamiast tabulatorów, liczba bajtów jest większa niż to konieczne. Na mojej maszynie jest to 9550 bajtów. (w momencie pisania tej wersji)- Następna sekwencja .
- Kod, w obecnej formie, drukuje tylko pierwsze 20 terminów sekwencji. Łatwo to jednak zmienić, aby wydrukować pierwsze 1000 elementów (poprzez zmianę
20w for (int i = 0; i < 20; ++i)na 1000)
Tak! Może to obliczyć więcej terminów niż te wymienione na stronie OEIS! (po raz pierwszy, dla wyzwania muszę używać Java), chyba że OEIS ma gdzieś więcej warunków ...
Szybkie wyjaśnienie
Objaśnienie opisu sekwencji.
Sekwencja pyta o liczbę wolnych nieplanarnych polenoidów z grupą symetrii C 2v , gdzie:
- polenoid: (model matematyczny węglowodorów polienowych) drzewa (lub w zdegenerowanym przypadku, pojedynczy wierzchołek) z mogą być osadzone w sieci sześciokątnej.
Weźmy na przykład drzewa
O O O O (3)
| \ / \
| \ / \
O --- O --- O O --- O O --- O
| \
| (2) \
(1) O O
Pierwszy nie może być osadzony w sześciokątnej kratce, podczas gdy drugi może. To szczególne osadzenie jest uważane za różne od trzeciego drzewa.
- nieplanarny polenoid: osadzanie drzew w taki sposób, że istnieją dwa zachodzące na siebie wierzchołki.
(2)a (3)drzewo powyżej jest płaskie. Ten jest jednak niepłaski:
O---O O
/ \
/ \
O O
\ /
\ /
O --- O
(jest 7 wierzchołków i 6 krawędzi)
- wolny polienoid: warianty jednego polienoidu, które można uzyskać przez obrót i odbicie, są liczone jako jeden.
- Grupa C 2v : Polienoidy są liczone tylko wtedy, gdy mają 2 prostopadłe płaszczyzny odbicia i nie więcej.
Na przykład jedyny polienoid z 2 wierzchołkami
O --- O
ma 3 płaszczyzny odbicia: poziomy -, pionowy |i równoległy do ekranu komputera ■. To za dużo.
Z drugiej strony ten
O --- O
\
\
O
ma 2 płaszczyzny refleksji: /i ■.
Objaśnienie metody
A teraz podejście do tego, jak liczyć liczbę.
Po pierwsze, biorę formułę a(n) = A000063(n + 2) - A000936(n)(wymienioną na stronie OEIS) za pewnik. Nie przeczytałem wyjaśnienia w gazecie.
[TODO napraw tę część]
Oczywiście liczenie planarne jest łatwiejsze niż liczenie niepłaskie. To właśnie robi papier.
Geometrycznie płaskie polenoidy (bez nakładających się wierzchołków) są wyliczane przez programowanie komputerowe. W ten sposób liczba geometrycznie niepłaskich polenoidów staje się dostępna.
Więc ... program zlicza liczbę płaskich polenoidów i odejmuje ją od sumy.
Ponieważ drzewo i tak jest płaskie, ma oczywiście ■płaszczyznę odbicia. Zatem warunek sprowadza się do „zliczenia liczby drzew z osią odbicia w ich reprezentacji 2D”.
Naiwnym sposobem byłoby wygenerowanie wszystkich drzew z nwęzłami i sprawdzenie poprawności symetrii. Ponieważ jednak chcemy znaleźć tylko liczbę drzew z osią odbicia, możemy po prostu wygenerować wszystkie możliwe pół-drzewa na jednej połowie, odbić je przez oś, a następnie sprawdzić poprawność symetrii. Ponadto, ponieważ generowane polioidy są drzewami (płaskimi), muszą dokładnie dotknąć osi odbicia.
Funkcja public static Graph[] expand(Graph[] graphs, Point.Predicate fn)pobiera tablicę wykresów, z których każdy ma nwęzły i wyprowadza tablicę wykresu, każdy ma n+1węzły, które nie są sobie równe (w tłumaczeniu) - tak, że dodany węzeł musi spełniać predykat fn.
Rozważ 2 możliwe osie odbicia: jedną przechodzącą przez wierzchołek i pokrywającą się z krawędziami ( x = 0) oraz drugą, która jest prostopadłą dwusieczną krawędzi ( 2x = y). Możemy wziąć tylko jeden z nich, ponieważ generowane wykresy są zresztą izomorficzne.
Tak więc, dla pierwszej osi x = 0, zaczynamy od wykresu podstawowego składającego się z pojedynczego węzła (1, 0)(w przypadku, gdy njest nieparzysty) lub dwóch węzłów z krawędzią pomiędzy (1, 0) - (2, 0)(w przypadku, gdy njest parzysty), a następnie rozwiń węzły, aby y > 0. Odbywa się to w sekcji programu „Typ odbicia 1”, a następnie dla każdego wygenerowanego wykresu odbij się (odbicie lustrzane) przez oś X x = 0( g.reflectSelfX()), a następnie sprawdź, czy ma prawidłową symetrię.
Zauważ jednak, że jeśli nmożna podzielić przez 2, w ten sposób policzyliśmy każdy wykres dwukrotnie, ponieważ generujemy również jego odbicie lustrzane według osi 2x = y + 3.
(zwróć uwagę na 2 pomarańczowe)
Podobnie dla osi 2x = y, jeśli (i tylko jeśli) njest parzysta, zaczynamy od punktu (1, 1), generujemy wykresy, które 2*x > yodbijają każdy z nich nad 2x = yosią ( g.reflectSelfType2()), łączymy (1, 0)się (1, 1)i sprawdzamy, czy mają prawidłową symetrię. Pamiętaj też o podzieleniu przez 2.
