From e86755d75f4040ae6619702a6501325ea81b03e1 Mon Sep 17 00:00:00 2001 From: Scott Worley Date: Tue, 29 Dec 2015 02:05:28 -0800 Subject: [PATCH] Switch from Go to C++ --- .gitignore | 3 ++ Makefile | 36 ++++++++++++++++ sliding_tile.cc | 4 ++ sliding_tile.go | 90 ---------------------------------------- sliding_tile_lib.cc | 0 sliding_tile_lib.h | 20 +++++++++ sliding_tile_lib_test.cc | 34 +++++++++++++++ sliding_tile_test.go | 70 ------------------------------- 8 files changed, 97 insertions(+), 160 deletions(-) create mode 100644 Makefile create mode 100644 sliding_tile.cc delete mode 100644 sliding_tile.go create mode 100644 sliding_tile_lib.cc create mode 100644 sliding_tile_lib.h create mode 100644 sliding_tile_lib_test.cc delete mode 100644 sliding_tile_test.go diff --git a/.gitignore b/.gitignore index b03b1b0..7cc0368 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,4 @@ sliding_tile +sliding_tile_lib_test +*.o +Makefile.bak diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..333a641 --- /dev/null +++ b/Makefile @@ -0,0 +1,36 @@ +CXX = g++ +CXXFLAGS = -std=gnu++11 -Wall -Wextra -pedantic -O2 +LFLAGS = + +SRCS = sliding_tile.cc sliding_tile_lib.cc +MAIN = sliding_tile +LIBS = +TESTLIBS = -lgtest_main -lgtest -lgmock + +OBJS = $(SRCS:.cc=.o) +TEST_SRCS=$(wildcard *_test.cc) +TESTS=$(subst .cc,,$(TEST_SRCS)) + +.PHONY: depend clean test +.INTERMEDIATE: $(OBJS) + +all: $(MAIN) $(TESTS) + +test: $(TESTS) + for t in ./*_test; do if ! $$t; then exit 1; fi ;done + +clean: + rm -f *.o $(MAIN) $(TESTS) + +$(MAIN): $(OBJS) + $(CXX) $(CXXFLAGS) -o $@ $^ $(LFLAGS) $(LIBS) + +%_test: %_test.o %.o + $(CXX) $(CXXFLAGS) -o $@ $^ $(LFLAGS) $(LIBS) $(TESTLIBS) + +depend: $(SRCS) + makedepend $^ + +# DO NOT DELETE THIS LINE -- make depend depends on it. + +sliding_tile.o: sliding_tile_lib.h diff --git a/sliding_tile.cc b/sliding_tile.cc new file mode 100644 index 0000000..4b7e917 --- /dev/null +++ b/sliding_tile.cc @@ -0,0 +1,4 @@ +#include "sliding_tile_lib.h" + +int main() { +} diff --git a/sliding_tile.go b/sliding_tile.go deleted file mode 100644 index 68cd4b1..0000000 --- a/sliding_tile.go +++ /dev/null @@ -1,90 +0,0 @@ -package main - -import "flag" -import "fmt" -import "os" -import "reflect" -import "strconv" - -import "github.com/petar/GoLLRB/llrb" -import "github.com/willf/bloom" - -var bloomsize = flag.Int("bloomsize", 2000000, "Size bloomfilter for this many states.") - -const HOLE = 0 -const BOARD_DIM = 4 -const BOARD_SIZE = BOARD_DIM * BOARD_DIM - -type Space int8 -type Board [BOARD_SIZE]Space -type Step struct { - board Board - prev *Step - length int -} - -const ( - LEFT = -1 - RIGHT = +1 - UP = -BOARD_DIM - DOWN = +BOARD_DIM -) - -func read_board_from_strings(in []string) (*Board, error) { - if len(in) != BOARD_SIZE { - return nil, fmt.Errorf("Please provide %d values", BOARD_SIZE) - } - var b Board - for i, s := range in { - num, err := strconv.Atoi(s) - b[i] = Space(num) - if err != nil { - return nil, err - } - } - return &b, nil -} - -func adjacent_spaces(s Space) []Space { - if s < 0 || s >= BOARD_SIZE { - panic("Invalid space") - } - var adjacent []Space - if s >= BOARD_DIM { - adjacent = append(adjacent, s+UP) - } - if s < BOARD_SIZE-BOARD_DIM { - adjacent = append(adjacent, s+DOWN) - } - if s%BOARD_DIM != 0 { - adjacent = append(adjacent, s+LEFT) - } - if s%BOARD_DIM != BOARD_DIM-1 { - adjacent = append(adjacent, s+RIGHT) - } - return adjacent -} - -func create_successors(start *Step) { - for _, adj := adjacent_spaces(start. -} - -func sliding_tile(start *Board) error { - seen := bloom.NewWithEstimates(uint(*bloomsize), 0.0001) - seen.Add(reflect.ValueOf(*start).Bytes()) - return nil -} - -func main() { - flag.Parse() - start, err := read_board_from_strings(flag.Args()) - if err != nil { - fmt.Println(err) - os.Exit(1) - } - err = sliding_tile(start) - if err != nil { - fmt.Println(err) - os.Exit(1) - } -} diff --git a/sliding_tile_lib.cc b/sliding_tile_lib.cc new file mode 100644 index 0000000..e69de29 diff --git a/sliding_tile_lib.h b/sliding_tile_lib.h new file mode 100644 index 0000000..7b16a51 --- /dev/null +++ b/sliding_tile_lib.h @@ -0,0 +1,20 @@ +const int BOARD_DIM = 4; +const int BOARD_SIZE = BOARD_DIM * BOARD_DIM; +signed char adjacent[BOARD_SIZE][5] = { + 1, 4, -1, -1, -1, + 0, 2, 5, -1, -1, + 1, 3, 6, -1, -1, + 2, 7, -1, -1, -1, + 0, 5, 8, -1, -1, + 1, 4, 6, 9, -1, + 2, 5, 7, 10, -1, + 3, 6, 11, -1, -1, + 4, 9, 12, -1, -1, + 5, 8, 10, 13, -1, + 6, 9, 11, 14, -1, + 7, 10, 15, -1, -1, + 8, 13, -1, -1, -1, + 9, 12, 14, -1, -1, + 10, 13, 15, -1, -1, + 11, 14, -1, -1, -1, +}; diff --git a/sliding_tile_lib_test.cc b/sliding_tile_lib_test.cc new file mode 100644 index 0000000..2050896 --- /dev/null +++ b/sliding_tile_lib_test.cc @@ -0,0 +1,34 @@ +#include "sliding_tile_lib.h" + +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include + +TEST(Adjacency, Adjacency) { + const signed char LEFT = -1; + const signed char RIGHT = +1; + const signed char UP = -BOARD_DIM; + const signed char DOWN = +BOARD_DIM; + for (int i = 0; i < BOARD_SIZE; i++) { + SCOPED_TRACE(i); + std::vector expected; + if (i >= BOARD_DIM) { + expected.push_back(i + UP); + } + if (i < BOARD_SIZE - BOARD_DIM) { + expected.push_back(i + DOWN); + } + if (i % BOARD_DIM != 0) { + expected.push_back(i + LEFT); + } + if (i % BOARD_DIM != BOARD_DIM - 1) { + expected.push_back(i + RIGHT); + } + + std::vector actual; + for (int j = 0; adjacent[i][j] >= 0; j++) { + actual.push_back(adjacent[i][j]); + } + EXPECT_THAT(actual, testing::UnorderedElementsAreArray(expected)); + } +} diff --git a/sliding_tile_test.go b/sliding_tile_test.go deleted file mode 100644 index 34f3fcc..0000000 --- a/sliding_tile_test.go +++ /dev/null @@ -1,70 +0,0 @@ -package main - -import "reflect" -import "sort" -import "testing" - -func Test_read_board_from_strings(t *testing.T) { - b, err := read_board_from_strings([]string{"1", "2", "9", "12", "6", "8", "13", "14", "0", "11", "15", "3", "7", "4", "10", "5"}) - if err != nil || *b != Board([BOARD_SIZE]Space{1, 2, 9, 12, 6, 8, 13, 14, 0, 11, 15, 3, 7, 4, 10, 5}) { - t.Fail() - } - - // Not enough - b, err = read_board_from_strings([]string{"1", "2", "9", "12", "6", "8", "13", "14", "0", "11", "15", "3", "7", "4", "10"}) - if err == nil { - t.Fail() - } - - // Not an integer - b, err = read_board_from_strings([]string{"1", "foo", "9", "12", "6", "8", "13", "14", "0", "11", "15", "3", "7", "4", "10", "5"}) - if err == nil { - t.Fail() - } - - // Empty string - b, err = read_board_from_strings([]string{"1", "", "9", "12", "6", "8", "13", "14", "0", "11", "15", "3", "7", "4", "10", "5"}) - if err == nil { - t.Fail() - } -} - -// For sorting, for unordered equality testing -type Spaces []Space - -func (s Spaces) Len() int { return len(s) } -func (s Spaces) Swap(i, j int) { s[i], s[j] = s[j], s[i] } -func (s Spaces) Less(i, j int) bool { return s[i] < s[j] } - -func Test_adjacent_spaces(t *testing.T) { - type TestCase struct { - s Space - expected Spaces - } - cases := []TestCase{ - {0, []Space{1, 4}}, - {1, []Space{0, 2, 5}}, - {2, []Space{1, 3, 6}}, - {3, []Space{2, 7}}, - {4, []Space{0, 5, 8}}, - {5, []Space{1, 4, 6, 9}}, - {6, []Space{2, 5, 7, 10}}, - {7, []Space{3, 6, 11}}, - {8, []Space{4, 9, 12}}, - {9, []Space{5, 8, 10, 13}}, - {10, []Space{6, 9, 11, 14}}, - {11, []Space{7, 10, 15}}, - {12, []Space{8, 13}}, - {13, []Space{9, 12, 14}}, - {14, []Space{10, 13, 15}}, - {15, []Space{11, 14}}, - } - for i, c := range cases { - var actual Spaces = adjacent_spaces(c.s) - sort.Sort(c.expected) - sort.Sort(actual) - if !reflect.DeepEqual(c.expected, actual) { - t.Error(i, c.expected, actual) - } - } -} -- 2.44.1