<commit_before>/**
 * Convert a set of aperiodic Wang tiles to an aperiodic set of "action" tiles.
 * A set of action tiles has 2 properties:
 * 1. The tiles are SE-identical.
 *    - South and east edge colors are the same.
 * 2. The set is W-disabling.
 *    - No two tiles having the same west edge color
 *      can be placed directly above/below each other
 *      (i.e., the north color of one tile differs from
 *      the south color of the other tile, and vice-versa).
 *
 * This particular tile set is NW-deterministic, and therefore the action
 * tiles can be used to create a deterministic unidirectional ring protocol
 * that always terminates from any initial state on any ring size,
 * but it is quite hard to prove!
 *
 * This reduction is tweaked from my paper:
 *   "Verifying Livelock Freedom on Parameterized Rings and Chains"
 *   http://dx.doi.org/10.1007/978-3-319-03089-0_12
 * See the paper or tech report for details about problem significance,
 * but see the comment above ReduceToActionTiles() for the new reduction.
 * It will eventually appear in a journal version.
 *
 **/
extern "C" {
#include "cx/syscx.h"
}
#include "cx/synhax.hh"

#include "cx/alphatab.hh"
#include "cx/map.hh"
#include "cx/ofile.hh"
#include "cx/set.hh"
#include "cx/table.hh"
#include "cx/tuple.hh"

using Cx::mk_Tuple;

// Tile set originally from:
//   Grunbaum and Shephard's 1986 book "Tilings and Patterns".
// I pulled it from:
//   <NAME>, and Culik's 1992 paper "The Topological Entropy of Cellular Automata is Uncomputable".
// It's also on Wikipedia as the size 16 set:
//   https://en.wikipedia.org/wiki/List_of_aperiodic_sets_of_tiles
// Edge colors are listed in order: west, north, south, east.
static const uint TileSet[][4] = {
//  W  N  S  E
  { 1, 1, 2, 2 },
  { 1, 5, 4, 1 },
  { 2, 3, 6, 2 },
  { 2, 4, 6, 1 },
  { 2, 5, 3, 1 },
  { 3, 2, 2, 6 },
  { 3, 3, 4, 4 },
  { 3, 4, 4, 5 },
  { 3, 6, 4, 3 },
  { 4, 2, 1, 6 },
  { 4, 3, 5, 4 },
  { 4, 4, 5, 5 },
  { 5, 1, 1, 4 },
  { 5, 2, 1, 3 },
  { 6, 3, 3, 4 },
  { 6, 6, 3, 3 }
};

/** Lookup/create a unique id for a symbol.
 *
 * A symbol is an array of color values from the input Wang tile set.
 **/
static
  uint
LookupSymId (Cx::Map< Cx::Table<uint>, uint >& idmap, const Cx::Table<uint>& key)
{
  return idmap.ensure(key, idmap.sz());
}

/** Populate {ret_acts}, return domain size.
 *
 * Each input Wang tile is converted to some action tiles by the following transformation:
 *                     ________ ________
 *                    |   b1   |    $   |
 *    ________        |        |        |
 *   |    b   |       |a0  abcd|abcd  d0|
 *   |        |       |        |        |
 *   |a      d|  -->  |__abcd__|___d0___|
 *   |        |       |  abcd  |   d0   |
 *   |____c___|       |        |        |
 *                    |$     c1|c1     $|
 *                    |        |        |
 *                    |___c1___|____$___|
 **/
static
  uint
ReduceToActionTiles (Cx::Table< Cx::Tuple<uint,3> >& ret_acts, const Cx::Table< Cx::Tuple<uint,4> >& tiles)
{
  Cx::Map< Cx::Table<uint>, uint > idmap;
  Cx::Set< Cx::Tuple<uint,3> > acts;

  // This is the $ symbol.
  const uint blank = LookupSymId (idmap, Cx::Table<uint>());

  // Reserve low symbol ids (i.e., action tile colors) in the action tile set
  // for those corresponding to Wang tile colors.
  {
    Cx::Set<uint> ri_colors, up_colors;
    for (uint tile_idx = 0; tile_idx < tiles.sz(); ++tile_idx) {
      const Cx::Tuple<uint,4>& tile = tiles[tile_idx];
      up_colors << tile[0] << tile[3];
      ri_colors << tile[1] << tile[2];
    }
    Cx::Set<uint>::const_iterator it;
    for (it = ri_colors.begin(); it != ri_colors.end(); ++it) {
      Cx::Table<uint> sym;
      LookupSymId (idmap, (sym << *it << 0));
    }
    for (it = up_colors.begin(); it != up_colors.end(); ++it) {
      Cx::Table<uint> sym;
      LookupSymId (idmap, (sym << *it << 1));
    }
  }

  for (uint tile_idx = 0; tile_idx < tiles.sz(); ++tile_idx) {
    const Cx::Tuple<uint,4>& tile = tiles[tile_idx];
    Cx::Table<uint> sym;

    sym << tile[0] << tile[1] << tile[2] << tile[3];
    const uint actcolor = LookupSymId (idmap, sym);

    sym.flush() << tile[0] << 0;
    const uint a_ri = LookupSymId (idmap, sym);

    sym.flush() << tile[1] << 1;
    const uint b_up = LookupSymId (idmap, sym);

    sym.flush() << tile[2] << 1;
    const uint c_up = LookupSymId (idmap, sym);

    sym.flush() << tile[3] << 0;
    const uint d_ri = LookupSymId (idmap, sym);

    acts << mk_Tuple(a_ri, b_up, actcolor);
    acts << mk_Tuple(blank, actcolor, c_up);
    acts << mk_Tuple(actcolor, blank, d_ri);
    acts << mk_Tuple(c_up, d_ri, blank);
  }
  acts.fill(ret_acts);
  return idmap.sz();
}

/** Execute me now!**/<commit_msg>Simplify some variable names in {unidomino}<commit_after>/**
 * Convert a set of aperiodic Wang tiles to an aperiodic set of "action" tiles.
 * A set of action tiles has 2 properties:
 * 1. The tiles are SE-identical.
 *    - South and east edge colors are the same.
 * 2. The set is W-disabling.
 *    - No two tiles having the same west edge color
 *      can be placed directly above/below each other
 *      (i.e., the north color of one tile differs from
 *      the south color of the other tile, and vice-versa).
 *
 * This particular tile set is NW-deterministic, and therefore the action
 * tiles can be used to create a deterministic unidirectional ring protocol
 * that always terminates from any initial state on any ring size,
 * but it is quite hard to prove!
 *
 * This reduction is tweaked from my paper:
 *   "Verifying Livelock Freedom on Parameterized Rings and Chains"
 *   http://dx.doi.org/10.1007/978-3-319-03089-0_12
 * See the paper or tech report for details about problem significance,
 * but see the comment above ReduceToActionTiles() for the new reduction.
 * It will eventually appear in a journal version.
 *
 **/
extern "C" {
#include "cx/syscx.h"
}
#include "cx/synhax.hh"

#include "cx/alphatab.hh"
#include "cx/map.hh"
#include "cx/ofile.hh"
#include "cx/set.hh"
#include "cx/table.hh"
#include "cx/tuple.hh"

using Cx::mk_Tuple;

// Tile set originally from:
//   Grunbaum and Shephard's 1986 book "Tilings and Patterns".
// I pulled it from:
//   <NAME>, and Culik's 1992 paper "The Topological Entropy of Cellular Automata is Uncomputable".
// It's also on Wikipedia as the size 16 set:
//   https://en.wikipedia.org/wiki/List_of_aperiodic_sets_of_tiles
// Edge colors are listed in order: west, north, south, east.
static const uint TileSet[][4] = {
//  W  N  S  E
  { 1, 1, 2, 2 },
  { 1, 5, 4, 1 },
  { 2, 3, 6, 2 },
  { 2, 4, 6, 1 },
  { 2, 5, 3, 1 },
  { 3, 2, 2, 6 },
  { 3, 3, 4, 4 },
  { 3, 4, 4, 5 },
  { 3, 6, 4, 3 },
  { 4, 2, 1, 6 },
  { 4, 3, 5, 4 },
  { 4, 4, 5, 5 },
  { 5, 1, 1, 4 },
  { 5, 2, 1, 3 },
  { 6, 3, 3, 4 },
  { 6, 6, 3, 3 }
};

/** Lookup/create a unique id for a symbol.
 *
 * A symbol is an array of color values from the input Wang tile set.
 **/
static
  uint
LookupSymId (Cx::Map< Cx::Table<uint>, uint >& idmap, const Cx::Table<uint>& key)
{
  return idmap.ensure(key, idmap.sz());
}

/** Populate {ret_acts}, return domain size.
 *
 * Each input Wang tile is converted to some action tiles by the following transformation:
 *                     ________ ________
 *                    |   b1   |    $   |
 *    ________        |        |        |
 *   |    b   |       |a0  abcd|abcd  d0|
 *   |        |       |        |        |
 *   |a      d|  -->  |__abcd__|___d0___|
 *   |        |       |  abcd  |   d0   |
 *   |____c___|       |        |        |
 *                    |$     c1|c1     $|
 *                    |        |        |
 *                    |___c1___|____$___|
 **/
static
  uint
ReduceToActionTiles (Cx::Table< Cx::Tuple<uint,3> >& ret_acts, const Cx::Table< Cx::Tuple<uint,4> >& tiles)
{
  Cx::Map< Cx::Table<uint>, uint > idmap;
  Cx::Set< Cx::Tuple<uint,3> > acts;

  // This is the $ symbol.
  const uint blank = LookupSymId (idmap, Cx::Table<uint>());

  // Reserve low symbol ids (i.e., action tile colors) in the action tile set
  // for those corresponding to Wang tile colors.
  {
    Cx::Set<uint> ri_colors, up_colors;
    for (uint tile_idx = 0; tile_idx < tiles.sz(); ++tile_idx) {
      const Cx::Tuple<uint,4>& tile = tiles[tile_idx];
      up_colors << tile[0] << tile[3];
      ri_colors << tile[1] << tile[2];
    }
    Cx::Set<uint>::const_iterator it;
    for (it = ri_colors.begin(); it != ri_colors.end(); ++it) {
      Cx::Table<uint> sym;
      LookupSymId (idmap, (sym << *it << 0));
    }
    for (it = up_colors.begin(); it != up_colors.end(); ++it) {
      Cx::Table<uint> sym;
      LookupSymId (idmap, (sym << *it << 1));
    }
  }

  for (uint tile_idx = 0; tile_idx < tiles.sz(); ++tile_idx) {
    const Cx::Tuple<uint,4>& tile = tiles[tile_idx];
    Cx::Table<uint> sym;

    sym << tile[0] << tile[1] << tile[2] << tile[3];
    const uint abcd = LookupSymId (idmap, sym);

    sym.flush() << tile[0] << 0;
    const uint a0 = LookupSymId (idmap, sym);

    sym.flush() << tile[1] << 1;
    const uint b1 = LookupSymId (idmap, sym);

    sym.flush() << tile[2] << 1;
    const uint c1 = LookupSymId (idmap, sym);

    sym.flush() << tile[3] << 0;
    const uint d0 = LookupSymId (idmap, sym);

    acts << mk_Tuple( a0    , b1    , abcd  );
    acts << mk_Tuple( blank , abcd  , c1    );
    acts << mk_Tuple( abcd  , blank , d0    );
    acts << mk_Tuple( c1    , d0    , blank );
  }
  acts.fill(ret_acts);
  return idmap.sz();
}

/** Execute me now!**/
{'fraction_non_alphanumeric': 0.15215341087708267, 'fraction_numerical': 0.028712145027769045, 'mean_word_length': 2.4269299820466785, 'pattern_counts': {'":': 0, '<': 143, '<?xml version=': 0, '>': 45, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 6, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2175832', 'n_tokens_mistral': 3716, 'n_tokens_neox': 3402, 'n_words': 1094}