JavaScript: 有理数を使ってテンパズルしてみた

こちらの記事がおもしろそうだったので自分でもやってみました。

今回は

• かっこを使わない
• (裏で)有理数を使って計算する
• 同じような式をあらかじめ間引く

ってことでやってみます。

かっこを使わないっていうのは、 一般的な10パズルのルールではないようです。
かっこを使った計算をしないってこともそうなんですが、かっこで計算の順序をコントロールするのではなく、左から順に、優先度が高いかけ算割り算から先に、っていう普通の算数の感じがやってみたかったってことです。

何で有理数(整数の分数ってことですね)を使うかっていうと、割り算があるので、ちょっとやりにくい部分(誤差がー、とか、0 で割るときはー、とか)があって、じゃあ全部有理数にしちゃえ! ってことです。

これ系で苦労するのは、沢山作っちゃったあとで同じようなものを取り除いていくことじゃないかなあと思います。今回はなるべく早い段階で被りを取り除いていこうと思います。

計算で使う汎用の関数

いろいろ必要そうなものを自前でそろえました。

// 順列と組合せ」：
// 共通の内部再帰関数
const innerPC = filterFunc => selecteds => k => options =>  
  (k === 0)? [selecteds]
  : options.flatMap(
      (e, i) =>
        innerPC( filterFunc )( [...selecteds, e] )( k-1 )( filterFunc(i)(options) ) 
    )

// 順列
const permFilter = i => options =>
  [...options.slice(0, i), ...options.slice(i + 1)]
const perm =  
  innerPC( permFilter )( [] )

// 組み合わせ
const combiFilter = i => options =>
  options.slice(i + 1)
const combi = 
  innerPC( combiFilter )( [] )

// 重複順列
const repPermFilter = i => options =>
  options
const repPerm = 
  innerPC( repPermFilter )( [] )

// 重複組み合わせ
const repCombiFilter = i => options =>
  options.slice(i)
const repCombi = 
  innerPC( repCombiFilter )( [] )

// 同値の配列を取り除く：
const unify = xss =>
  xss.reduce((acc, xs, i, a) => 
             acc.some(equals(xs)) 
             ? acc 
             : [...acc, xs]
           , []
           )
const equals = xs => ys =>
  Array.isArray(xs) 
  && Array.isArray(ys) 
  && xs.length === ys.length 
  && xs.every( (x, i) => x === ys[i])

// 最大公約数：
const gcd = x => y =>
  y === 0 
  ? NaN  
  : x % y === 0 
  ? y
  : gcd(y)(x % y)

// 長い方に合わせてzip：
const zipLonger = xs => ys =>
  xs.length >= ys.length 
  ? xs.map( (e, i) => i >= ys.length 
                          ? [e]
                          : [ e, ys[i] ]
  )
  : ys.map( (e, i) => i >= xs.length 
                          ? [e]
                          : [ xs[i], e ]
  )

有理数

分母と分子がはいってるオブジェクトです。
分母に 0 がきたら、分母も分子も NaN になります。
作るときに約分してくれる優れ物です。(ここではあんまり意味はないですが)

// 有理数：
const frac = denom => num =>{
  if(isNaN(num) || isNaN(denom) || denom === 0 ){ 
    return {denom: NaN, num: NaN}
  }
  const common = gcd(num)(denom)
  return {denom: Math.floor(denom / common)
          , num: Math.floor(num / common)
         }
}
const retFrac = frac(1)

const isFrac = x =>
  x.hasOwnProperty('denom') 
  && x.hasOwnProperty('num') 

const evalFrac = a =>
  ! isFrac(a)
  ? NaN

  : a.denom === 1
  ? a.num

  : a.num / a.denom

const showFrac = a =>
  evalFrac(a).toString()

演算

分母と分子を別々に計算して新たに有理数を作って返します。
分子が 0 の有理数で割ると結果的に分母分子が NaNの有理数が返されます。
それぞれ、優先度と表示と id を設定してます。

// 演算：
const add = x =>  y => 
  ! [x, y].every(isFrac)
  ? frac(NaN)(NaN)
  : frac(x.denom * y.denom)
      (x.num * y.denom + y.num * x.denom)

const sub = x =>  y =>
  ! [x, y].every(isFrac)
  ? frac(NaN)(NaN)
  : frac(x.denom * y.denom)
      (x.num * y.denom - y.num * x.denom)

const mul = x =>  y =>
  ! [x, y].every(isFrac)
  ? frac(NaN)(NaN)
  : frac(x.denom * y.denom)(x.num * y.num)

const div = x =>  y =>
  ! [x, y].every(isFrac)
  ? frac(NaN)(NaN)
  : frac(x.denom * y.num)(x.num * y.denom)

add.prior = false
add.show = "+"
add.id = 0

sub.prior = false
sub.show ="-"
sub.id = 1

mul.prior = true
mul.show = "*"
mul.id = 2

div.prior = true
div.show = "/"
div.id = 3

const OPS = [add, sub, mul, div]

const isOps = x =>
  OPS.includes(x)

数式

演算の配列と有理数の配列がはいってるオブジェクトです。
最終的に人が見るときだけ、数式っぽい文字列にします。

// 数式：
const expression = ops => fracs =>
  ({ops: ops, fracs: fracs})

const retExp = ops => nums =>
  expression(ops)(nums.map(retFrac))

const evalExp = exp =>
  evalFrac( calc(exp) )

const showExp = exp =>
  zipLonger(exp.fracs)(exp.ops)
  .flat()
  .map(show)
  .join(" ")

const show = x =>
  isOps(x)
  ? x.show
  : showFrac(x)

計算

左端から、優先度の低い演算は保留して、優先度の高い演算を一個だけして先頭に戻り、優先度の低い演算だけになったら一気に計算してます。

const _calc = n => exp =>
  exp.fracs.length === 1 
  ? exp.fracs[0]

  : exp.ops[n].prior 
  ? _calc(0)( expression([ ...exp.ops.slice(0, n), ...exp.ops.slice(n + 1) ])
                        ([ ...exp.fracs.slice(0, n )
                         , exp.ops[n]( exp.fracs[n] )( exp.fracs[n + 1] )
                         , ...exp.fracs.slice(n + 2)
                         ]
                        )
            )

  : n === exp.ops.length - 1
  ? exp.fracs.slice(1)
    .reduce((acc, e, i) => exp.ops[i](acc)(e)
            , exp.fracs[0]
           )

  : _calc(n + 1)(exp)

const calc = _calc(0)

演算の配列の配列

総当たりでやると 4 * 4 * 4 = 64通りになります。なるべく被りを間引いていきます。
だいたいは重複組合せに含まれてるのですが、もれてるのがあるのでそれを足してます。

// 交換法則を考慮した全ての演算の配列
const OPS_LIST = 
       repPerm(3)(OPS)
        .filter( es => 
                es[0].id <= es[1].id && es[1].id <= es[2].id
                || es[0].prior && es[1] === add && es[2].prior && es[0].id <= es[2].id
                || es[0].prior && es[1] === sub && es[2] !== add
                || es[0].prior && es[1].prior && es[0].id <= es[1].id && es[2] === sub
                )

条件は：

• + - * / の順に並んでいる (重複組み合わせ相当)
• 要素は同じだけど、並びかえると違う数式になってしまうもの。
  • 例： [add, mul, mul] と [mul, add, mul]
• 交換法則がはたらかないもの
  • 例： [sub, mul, mul] と [mul, mul, sub]

です。
全部で 20 + 12 = 32 通りになりました。総当たりの半分です。

数の配列の配列

総当たりするとすると、ひとつの数の配列あたり 4 * 3 * 2 * 1 = 24通りになります。これを 演算の配列の配列と総当たりをすると、24 * 64 = 1536通りになります。
これも間引いていきます。

ひとつの演算の配列が決まると、交換法則を考慮して、ひとつの数の配列から、お互いかぶらないような数の配列の配列が決まります。

• 四つの数の順列を生成し
• 数の配列に同じ要素があると同じ配列ができてしまうので、あらかじめ間引いておき
• 条件に合うものを選ぶ

条件は：

• 一個目は何でもok
• a * b なら必ず交換法則がはたらくので、a ≤ b
• a / b / c なら / b と / c は交換可能なので、b ≤ c
• a + b で 次が優先度低いか、最後なら a ≤ b
• a - b - c で 次が優先度低いか、最後なら b ≤ c
• それ以外は何でもok

加えて：

• 真ん中が + で 最初と最後が優先度高くかつ同じ場合、+ の前と後を部分的に計算して、前 ≤ 後
  • a * b + c * d なら a * b ≤ c * d
  • a / b + c / d なら a / b ≤ c / d
• それ以外は何でもok

// 演算に対応した数の配列を生成する：
const uniqsList = ops => nums =>
  unify( perm(4)(nums) )
  .filter( e => e.every( (d, i, a) => 
                  i === 0 
                  ? true

                  : ops[i - 1] === mul
                  || i > 1 && ops[i - 2] === div && ops[i - 1] === div 
                  || (i < a.length - 1 && ! ops[i].prior || i === a.length - 1) 
                    && ops[i - 1] === add
                  || (i > 1 && i < a.length - 1  && ! ops[i].prior || i === a.length - 1)
                    && ops[i - 2] === sub && ops[i - 1] === sub  
                  ?  d >= a[i - 1]    

                  : true
                )   
                && ( ops[1] === add && ops[0].prior && ops[0] === ops[2] 
                      ? evalExp( retExp( ops.slice(0, 1) )( e.slice(0, 2) ) )
                        <= evalExp( retExp( ops.slice(2) )( e.slice(2) ) )

                      : true
                   )
  )

これをすると、だいぶ間引くことができます。実際に OPS_LIST と総当たりをしてみると、数の組み合わせによって違うのですが：

• 四つとも違う数だと 285 通り(0 を含むと 279)
• ワンペアだと 170 通り(0 を含むと 167)
• ツーペアだと 105 通り(0 を含むと 101)
• スリーカードだと 78 通り(0 を含むと 77)
• フォーカードだと 32 通り(0 を含むと 31)

になります。真の総当たりと比較すると 1/5 ~ 1/50 といったところでしょうか。

計算してみる

• すべての演算の配列に対して
• おたがいにかぶらないような数の配列の配列を作り
• 数式を作って
• 式を評価してターゲットと同じなら
• 文字列にして返す

みたいなことです。

// 使用例:
const target = 10
const nums = [1, 1, 3, 3]

const makeTen = target => nums => 
  OPS_LIST
  .flatMap( ops => uniqsList(ops)(nums) 
                   .map(retExp(ops))
                   .flatMap( exp => evalExp(exp) === target 
                                     ? [showExp(exp)] 
                                     : []
                           )
          )

makeTen(target)(nums)
/*  
[ '1 + 1 * 3 * 3'
, '1 + 3 * 3 / 1'
, '1 * 1 + 3 * 3'
, '3 * 3 + 1 / 1'
]
*/

やったーできたー!なかなかいい感じではないでしょうか。

ここがおかしいよ、とかコメントよろしくです。